Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log2 n) space requirements and O(log3 n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(log N + t) query time, O(n log2 N) space and O(log2 N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique. © 1985.
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Nanda Kambhatla
ACL 2004
Gal Badishi, Idit Keidar, et al.
IEEE TDSC
Qing Li, Zhigang Deng, et al.
IEEE T-MI