Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep

Yi Jen Chiang

doi:10.1007/3-540-60220-8_75

Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep

Yi Jen Chiang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present an extensive experimental study comparing the performance of four algorithms for the orthogonal segment intersection problem. The algorithms under evaluation are distribution sweep, which has optimal I/O cost, and three variations of plane sweep, which is optimal in terms of internal computation. We generate the test data by using a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms. This is the first experimental work comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings
Editors	Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	346-357
Number of pages	12
ISBN (Print)	3540602208, 9783540602200
DOIs	https://doi.org/10.1007/3-540-60220-8_75
State	Published - 1995
Event	4th Workshop on Algorithms and Data Structures, WADS 1995 - Kingston, Canada Duration: Aug 16 1995 → Aug 18 1995

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	955
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th Workshop on Algorithms and Data Structures, WADS 1995
Country/Territory	Canada
City	Kingston
Period	8/16/95 → 8/18/95

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-60220-8_75

Cite this

Chiang, Y. J. (1995). Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep. In S. G. Akl, F. Dehne, J.-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings (pp. 346-357). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 955). Springer Verlag. https://doi.org/10.1007/3-540-60220-8_75

Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep. / Chiang, Yi Jen.
Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. ed. / Selim G. Akl; Frank Dehne; Jörg-Rüdiger Sack; Nicola Santoro. Springer Verlag, 1995. p. 346-357 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 955).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chiang, YJ 1995, Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep. in SG Akl, F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 955, Springer Verlag, pp. 346-357, 4th Workshop on Algorithms and Data Structures, WADS 1995, Kingston, Canada, 8/16/95. https://doi.org/10.1007/3-540-60220-8_75

Chiang YJ. Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep. In Akl SG, Dehne F, Sack JR, Santoro N, editors, Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. Springer Verlag. 1995. p. 346-357. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-60220-8_75

Chiang, Yi Jen. / Experiments on the practical I/O efficiency of geometric algorithms : Distribution sweep vs. Plane sweep. Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. editor / Selim G. Akl ; Frank Dehne ; Jörg-Rüdiger Sack ; Nicola Santoro. Springer Verlag, 1995. pp. 346-357 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{79ec6ae0823c491f9eba38aa4dbff79f,

title = "Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep",

abstract = "We present an extensive experimental study comparing the performance of four algorithms for the orthogonal segment intersection problem. The algorithms under evaluation are distribution sweep, which has optimal I/O cost, and three variations of plane sweep, which is optimal in terms of internal computation. We generate the test data by using a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms. This is the first experimental work comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.",

author = "Chiang, {Yi Jen}",

year = "1995",

doi = "10.1007/3-540-60220-8_75",

language = "English (US)",

isbn = "3540602208",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "346--357",

editor = "Akl, {Selim G.} and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings",

}

TY - GEN

T1 - Experiments on the practical I/O efficiency of geometric algorithms

T2 - 4th Workshop on Algorithms and Data Structures, WADS 1995

AU - Chiang, Yi Jen

PY - 1995

Y1 - 1995

N2 - We present an extensive experimental study comparing the performance of four algorithms for the orthogonal segment intersection problem. The algorithms under evaluation are distribution sweep, which has optimal I/O cost, and three variations of plane sweep, which is optimal in terms of internal computation. We generate the test data by using a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms. This is the first experimental work comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.

AB - We present an extensive experimental study comparing the performance of four algorithms for the orthogonal segment intersection problem. The algorithms under evaluation are distribution sweep, which has optimal I/O cost, and three variations of plane sweep, which is optimal in terms of internal computation. We generate the test data by using a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms. This is the first experimental work comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data.

UR - http://www.scopus.com/inward/record.url?scp=21844519976&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21844519976&partnerID=8YFLogxK

U2 - 10.1007/3-540-60220-8_75

DO - 10.1007/3-540-60220-8_75

M3 - Conference contribution

AN - SCOPUS:21844519976

SN - 3540602208

SN - 9783540602200

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 346

EP - 357

BT - Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings

A2 - Akl, Selim G.

A2 - Dehne, Frank

A2 - Sack, Jörg-Rüdiger

A2 - Santoro, Nicola

PB - Springer Verlag

Y2 - 16 August 1995 through 18 August 1995

ER -

Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. Plane sweep

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this