Selection by rank in K‐dimensional binary search trees. Issue 1 (6th December 2012)

• Record Type: Journal Article
• Authors: Duch, Amalia; Jiménez, Rosa M.; Martínez, Conrado
• Is Part Of: Random structures & algorithms. Volume 45:Issue 1(2014)
• Page Start: 14
• Page End: 37
• Publication Date: 2012-12-06
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20476
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>In this work we show how to augment general purpose multidimensional data structures, such as <italic>K</italic>‐d trees, to efficiently support search by rank (that is, to locate the <italic>i</italic>‐th smallest element along the <italic>j</italic>‐th coordinate, for given <italic>i</italic> and <italic>j</italic>) and to find the rank of a given item along a given coordinate. To do so, we introduce two simple, practical and very flexible algorithms – Select‐by‐Rank and Find‐Rank – with very little overhead. Both algorithms can be easily implemented and adapted to several spatial indexes, although their analysis is far from trivial. We are able to show that for random <italic>K</italic>‐d trees of size <italic>n</italic> the expected number of nodes visited by Find‐Rank is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs88hk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>P</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>K</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs88j3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> or <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs87zt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs87x9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>P</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>i</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mi>f</mml:mi><mml:mi>K</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>i</mml:mi><mml:mo>/</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>·</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mo>α</mml:mo></mml:msup><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mo>α</mml:mo></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs882v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mi>x</mml:mi><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> (with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs881b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>0</mml:mn><mml:mo><</mml:mo><mml:mi>x</mml:mi><mml:mo><</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>), where <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs884w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>K</mml:mi><mml:mo>≤</mml:mo><mml:mo>α</mml:mo><mml:mo><</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> depends on the dimension <italic>K</italic> and the variant of <italic>K</italic>‐d tree under consideration. We also show that Select‐by‐Rank visits <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs883c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>g</mml:mi><mml:mi>K</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>i</mml:mi><mml:mo>/</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>·</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mo>α</mml:mo></mml:msup><mml:mi>ln</mml:mi><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mi mathvariant="script">O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mo>α</mml:mo></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> nodes on average, where <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs885d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mi>x</mml:mi><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is the given rank and the exponent α is as above. We give the explicit form of the functions <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs87v8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mi>K</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs87ws" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20476:rsa20476-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>g</mml:mi><mml:mi>K</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, both are bounded in [0, 1] and they depend on <italic>K</italic>, on the variant of <italic>K</italic>‐d tree under consideration, and, eventually, on the specific coordinate <italic>j</italic> for which we execute our algorithms. As a byproduct of the analysis of our algorithms, but no less important, we give the average‐case analysis of a partial match search in random <italic>K</italic>‐d trees when the query is not random. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 14–37, 2014</p> </abstract>