dba@blic.BLI.COM (DB Administrator) (06/26/87)
I am looking for some advise. I have a database which has 100,000 line segments in it. A line segment includes a textual attribute and two xy coordinate pairs. The xy coords range from (0,0) to (50000,50000). If I define my current coordinate system to be from (200,200) to (300,300) how can the line segments that plot on this coordinate system be identified quickly? Sorting by xy only gets those segments that have at least one end point inside the current coordinate system. Thanks, ---greg
timos@mimsy.UUCP (06/29/87)
In article <117@blic.BLI.COM> dba@blic.BLI.COM (DB Administrator) writes: >I am looking for some advise. I have a database which has 100,000 >line segments in it. A line segment includes a textual attribute and >two xy coordinate pairs. The xy coords range from (0,0) to (50000,50000). >If I define my current coordinate system to be from (200,200) to (300,300) >how can the line segments that plot on this coordinate system be identified >quickly? Sorting by xy only gets those segments that have at least one >end point inside the current coordinate system. > >Thanks, >---greg I believe the most successfull methods are the Grid file [TODS 84] and Guttman's R-trees [Sigmod 84]. They both can be used as indexing methods for line segments. -- Timos Sellis CS Dept, University of Maryland, College Park, MD 20742 ARPA:timos@mimsy.umd.edu UUCP:{decvax,allegra,...}!mimsy!timos -- Timos Sellis CS Dept, University of Maryland, College Park, MD 20742 ARPA:timos@mimsy.umd.edu UUCP:{decvax,allegra,...}!mimsy!timos
jack@cca.UUCP (06/29/87)
Keywords: In article <117@blic.BLI.COM> dba@blic.BLI.COM (DB Administrator) writes: >I am looking for some advise. I have a database which has 100,000 >line segments in it. A line segment includes a textual attribute and >two xy coordinate pairs. The xy coords range from (0,0) to (50000,50000). >If I define my current coordinate system to be from (200,200) to (300,300) >how can the line segments that plot on this coordinate system be identified >quickly? Sorting by xy only gets those segments that have at least one >end point inside the current coordinate system. > >Thanks, >---greg See "A Class of Data Structures for Associative Searching" by Orenstein and Merrett in the proceedings of the 1984 SIGACT-SIGMOD symposium on Principles of Database Systems, and "Spatial Query Processing in an Object-Oriented Database System", by Orenstein in the proceedings of the 1986 SIGMOD conference. These papers show how any data structure or file organization that supports random and sequential accessing (e.g. binary tree, AVL tree, B-tree) can be used to support spatial queries. The earlier paper deals with "range queries" (find all the points in a box) while the later paper talks about more general queries in which the data objects and the query objects may be arbitrary shapes. Jack Orenstein