Abstract
Let \(\mathcal {T}\) be a tree space represented by a weighted tree with t vertices, and S be a set of n stochastic points in \(\mathcal {T}\), each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we propose the first algorithm of computing the \(\ell \)-threshold probability and the expectation of the closest-pair distance of a realization of S. For the latter, we study the k most-likely nearest-neighbor search (k-LNN) via a notion called the k most-likely Voronoi Diagram (k-LVD), where we show the combinatorial complexity of k-LVD is O(nk) under two reasonable assumptions, leading to a logarithmic query time for k-LNN.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agarwal, P., Aronov, B., Har-Peled, S., Phillips, J., Yi, K., Zhang, W.: Nearest neighbor searching under uncertainty II. In: Proc. of the 32nd Sympos. on PODS, pp. 115–126. ACM (2013)
Agarwal, P., Cheng, S.W., Yi, K.: Range searching on uncertain data. ACM Transactions on Algorithms 8(4), 43 (2012)
Agarwal, P.K., Har-Peled, S., Suri, S., Yıldız, H., Zhang, W.: Convex hulls under uncertainty. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 37–48. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44777-2_4
Agarwal, P., Kumar, N., Sintos, S., Suri, S.: Range-max queries on uncertain data. In: Proc. of the 35th SIGMOD/PODS, pp. 465–476. ACM (2016)
Chen, J., Feng, L.: Efficient pruning algorithm for top-k ranking on dataset with value uncertainty. In: Proc. of the 22nd CIKM, pp. 2231–2236. ACM (2013)
Fakcharoenphol, J., Rao, S., Talwar, K.: Approximating metrics by tree metrics. ACM SIGACT News 35(2), 60–70 (2004)
Fink, M., Hershberger, J., Kumar, N., Suri, S.: Hyperplane separability and convexity of probabilistic point sets. In: Proc. of the 32nd SoCG. ACM (2016)
Ge, T., Zdonik, S., Madden, S.: Top-\(k\) queries on uncertain data: on score distribution and typical answers. In: Proc. of the 2009 SIGMOD, pp. 375–388. ACM (2009)
Huang, L., Li, J.: Approximating the expected values for combinatorial optimization problems over stochastic points. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 910–921. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47672-7_74
Kamousi, P., Chan, T., Suri, S.: Stochastic minimum spanning trees in Euclidean spaces. In: Proc. of the 27th SoCG, pp. 65–74. ACM (2011)
Kamousi, P., Chan, T., Suri, S.: Closest pair and the post office problem for stochastic points. Computational Geometry 47(2), 214–223 (2014)
Kumar, N., Raichel, B., Suri, S., Verbeek, K.: Most likely Voronoi Diagrams in higher dimensions. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 65. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)
Löffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235–269 (2010)
Suri, S., Verbeek, K.: On the most likely Voronoi Diagram and nearest neighbor searching. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 338–350. Springer, Cham (2014). doi:10.1007/978-3-319-13075-0_27
Suri, S., Verbeek, K., Yıldız, H.: On the most likely convex hull of uncertain points. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 791–802. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40450-4_67
Xue, J., Li, Y., Janardan, R.: On the separability of stochastic geometric objects, with applications. In: Proc. of the 32nd SoCG. ACM (2016)
Xue, J., Li, Y.: Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces. arXiv:1612.04890 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Xue, J., Li, Y. (2017). Stochastic Closest-Pair Problem and Most-Likely Nearest-Neighbor Search in Tree Spaces. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_48
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_48
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)