On Indexing Line Segments.

H. V. Jagadish: On Indexing Line Segments. VLDB 1990: 614-625
  author    = {H. V. Jagadish},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {On Indexing Line Segments},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {614-625},
  ee        = {db/conf/vldb/Jagadish90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP,}


In several image applications, it is necessary to retrieve specific line segments born a potentially very large set. In this paper, we consider the problem of indexing straight line segments to enable efficient retrieval of all line segments that (i) go through a specified point, or (ii) intersect a specified line segment. We propose a data organization, based on the Hough transform, that can be used to solve both retrieval problems efficiently. In addition, the proposed structure can be used for approximate retrievals, finding all line segments that pass close to a specified point. We show, through analysis and experiment, that the proposed technique always does as well as or better than retrieval based on minimum bounding rectangles or line segment end-points.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X


Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113 BibTeX
H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 BibTeX
Rangachar Kasturi, Juan Alemany: Information Extraction of Paper-Based Maps. IEEE Trans. Software Eng. 14(5): 671-675(1988) BibTeX
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX
Nick Roussopoulos, Christos Faloutsos, Timos K. Sellis: An Efficient Pictorial Database System for PSQL. IEEE Trans. Software Eng. 14(5): 639-650(1988) BibTeX
Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. ACM Comput. Surv. 20(4): 271-309(1988) BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
Peter M. Will, Keith S. Pennington: Grid Coding: A Preprocessing Technique for Robot and Machine Vision. Artif. Intell. 2(3/4): 319-329(1971) BibTeX

Referenced by

  1. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  2. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  3. Brian C. Schmult, H. V. Jagadish, S. Kicha Ganapathy: Interactive Spatial Directories. IEEE Data Eng. Bull. 16(3): 22-27(1993)
  4. Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:46 2009