518 results on '"Range tree"'
Search Results
2. On the Minimum Consistent Subset Problem
- Author
-
Biniaz, Ahmad, Cabello, Sergio, Carmi, Paz, De Carufel, Jean-Lou, Maheshwari, Anil, Mehrabi, Saeed, Smid, Michiel, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Friggstad, Zachary, editor, Sack, Jörg-Rüdiger, editor, and Salavatipour, Mohammad R, editor more...
- Published
- 2019
- Full Text
- View/download PDF
Catalog
3. Multidimensional Range Selection
- Author
-
Chan, Timothy M., Zhou, Gelin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Elbassioni, Khaled, editor, and Makino, Kazuhisa, editor more...
- Published
- 2015
- Full Text
- View/download PDF
4. GPU Accelerated Range Trees with Applications
- Author
-
Maramreddy, Manoj Kumar, Kothapalli, Kishore, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Silva, Fernando, editor, Dutra, Inês, editor, and Santos Costa, Vítor, editor more...
- Published
- 2014
- Full Text
- View/download PDF
5. Sorted Range Reporting
- Author
-
Nekrich, Yakov, Navarro, Gonzalo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fomin, Fedor V., editor, and Kaski, Petteri, editor more...
- Published
- 2012
- Full Text
- View/download PDF
6. Path Queries in Weighted Trees
- Author
-
He, Meng, Munro, J. Ian, Zhou, Gelin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Asano, Takao, editor, Nakano, Shin-ichi, editor, Okamoto, Yoshio, editor, and Watanabe, Osamu, editor more...
- Published
- 2011
- Full Text
- View/download PDF
7. The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions : (Extended Abstract)
- Author
-
Backer, Jonathan, Keil, J. Mark, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and López-Ortiz, Alejandro, editor more...
- Published
- 2010
- Full Text
- View/download PDF
8. Space Efficient Multi-dimensional Range Reporting
- Author
-
Karpinski, Marek, Nekrich, Yakov, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Ngo, Hung Q., editor more...
- Published
- 2009
- Full Text
- View/download PDF
9. Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric
- Author
-
Atallah, Mikhail J., Blanton, Marina, Goodrich, Michael T., Polu, Stanislas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, and Zeh, Norbert, editor more...
- Published
- 2007
- Full Text
- View/download PDF
10. An Efficient Implementation of RBF-Based Progressive Point-Sampled Geometry
- Author
-
Liu, Yong-Jin, Tang, Kai, Ajay, Joneja, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kim, Myung-Soo, editor, and Shimada, Kenji, editor more...
- Published
- 2006
- Full Text
- View/download PDF
11. Preprocessing Convex Polygons Using Range Trees for Recognition with Few Finger Probes
- Author
-
Guha, Sumanta, Khánh, Kiêu Trọng, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gagalowicz, André, editor, and Philips, Wilfried, editor more...
- Published
- 2005
- Full Text
- View/download PDF
12. Privacy-Preserving Efficient Data Retrieval in IoMT Based on Low-Cost Fog Computing
- Author
-
Yuanyuan Cai, Na Wang, Junsong Fu, and Jie Xu
- Subjects
020203 distributed computing ,Multidisciplinary ,Article Subject ,General Computer Science ,Database ,business.industry ,Computer science ,Process (computing) ,QA75.5-76.95 ,02 engineering and technology ,computer.software_genre ,Range tree ,Upload ,Data retrieval ,Electronic computers. Computer science ,Ciphertext ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,The Internet ,Latency (engineering) ,business ,computer ,Bat algorithm - Abstract
The rapid development of Internet of Medical Things (IoMT) is remarkable. However, IoMT faces many problems including privacy disclosure, long delay of service orders, low retrieval efficiency of medical data, and high energy cost of fog computing. For these, this paper proposes a data privacy protection and efficient retrieval scheme for IoMT based on low-cost fog computing. First, a fog computing system is located between a cloud server and medical workers, for processing data retrieval requests of medical workers and orders for controlling medical devices. Simultaneously, it preprocesses physiological data of patients uploaded by IoMT, collates them into various data sets, and transmits them to medical institutions in this way. It makes the entire execution process of low latency and efficient. Second, multidimensional physiological data are of great value, and we use ciphertext retrieval to protect privacy of patient data in this paper. In addition, this paper uses range tree to build an index for storing physiological data vectors, and meanwhile a range retrieval method is also proposed to improve data search efficiency. Finally, bat algorithm (BA) is designed to allocate cost on a fog server group for significant energy cost reduction. Extensive experiments are conducted to demonstrate the efficiency of the proposed scheme. more...
- Published
- 2021
- Full Text
- View/download PDF
13. Range Tree
- Author
-
Cantoni, Virginio, Mattia, Elio, Dubitzky, Werner, editor, Wolkenhauer, Olaf, editor, Cho, Kwang-Hyun, editor, and Yokota, Hiroki, editor
- Published
- 2013
- Full Text
- View/download PDF
14. Partition Based Path Join Algorithms for XML Data
- Author
-
Li, Quanzhong, Moon, Bongki, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Mařík, Vladimír, editor, Retschitzegger, Werner, editor, and Štěpánková, Olga, editor
- Published
- 2003
- Full Text
- View/download PDF
15. Multiple Genome Alignment: Chaining Algorithms Revisited
- Author
-
Abouelhoda, Mohamed Ibrahim, Ohlebusch, Enno, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Baeza-Yates, Ricardo, editor, Chávez, Edgar, editor, and Crochemore, Maxime, editor more...
- Published
- 2003
- Full Text
- View/download PDF
16. Output-sensitive generation of the perspective view of isothetic parallelepipeds
- Author
-
Preparata, Franco P., Vitter, Jeffrey Scott, Yvinec, Mariette, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Gilbert, John R., editor, and Karlsson, Rolf, editor more...
- Published
- 1990
- Full Text
- View/download PDF
17. Locate a Pair Squares for Maximum Points Containment.
- Author
-
Mahapatra, Priya Ranjan Sinha
- Subjects
HYPERSPACE ,ALGORITHMS ,SQUARE ,COMPUTER programming ,ALGEBRA - Abstract
Given a set P of n points in R²: , locate two disjoint or overlapping axis-parallel squares, say S
1 and S2 , covering maximum number of points from P . However, in case of overlapping, their overlapped zone is empty. This work proposes O (n² log n) time and O (n²) space algorithm to locate S1 and S2 . [ABSTRACT FROM AUTHOR] more...- Published
- 2011
18. On finding the Adams consensus tree
- Author
-
Wing-Kin Sung, Jesper Jansson, and Zhaoxian Li
- Subjects
0301 basic medicine ,Tree rotation ,K-ary tree ,AVL tree ,Segment tree ,0102 computer and information sciences ,Interval tree ,01 natural sciences ,Search tree ,Computer Science Applications ,Theoretical Computer Science ,Range tree ,Combinatorics ,03 medical and health sciences ,030104 developmental biology ,Tree structure ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Information Systems ,Mathematics - Abstract
This article presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels. Its worst-case running time is O ( k n log n ) , where k is the number of input trees and n is the size of the leaf label set; in comparison, the original algorithm of Adams has a worst-case running time of O ( k n 2 ) . To achieve subquadratic running time, the centroid path decomposition technique is applied in a novel way that traverses the input trees by following a centroid path in each of them in unison. For k = 2 , an even faster algorithm running in O ( n ⋅ log n log log n ) time is provided, which relies on an extension of the wavelet tree-based technique of Bose et al. for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum/minimum queries efficiently. more...
- Published
- 2017
- Full Text
- View/download PDF
19. Fast approximations for sums of distances, clustering and the Fermat–Weber problem
- Author
-
Bose, Prosenjit, Maheshwari, Anil, and Morin, Pat
- Subjects
- *
EUCLIDEAN algorithm , *AGGLOMERATION (Materials) - Abstract
We describe two data structures that preprocess a set
S ofn points inRd (d constant) so that the sum of Euclidean distances of points inS to a query pointq</f> can be quickly approximated to within a factor of ϵ . This preprocessing technique has several applications in clustering and facility location. Using it, we derive anO(nlogn) time deterministic andO(n) time randomizedϵ -approximation algorithm for the so called Fermat–Weber problem in any fixed dimension. [Copyright &y& Elsevier] more...- Published
- 2003
- Full Text
- View/download PDF
20. Hash-based OpenFlow Packet Classification on Heterogeneous System Architecture
- Author
-
Tung-Yin Chi and Yeim-Kuan Chang
- Subjects
Heterogeneous System Architecture ,OpenFlow ,Network architecture ,Computer science ,business.industry ,Hash function ,Packet forwarding ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Hash table ,020202 computer hardware & architecture ,Range tree ,010201 computation theory & mathematics ,Wildcard ,0202 electrical engineering, electronic engineering, information engineering ,business ,Computer network - Abstract
Packet classification is a very important component for today's network architecture. It can help or provide packet forwarding and other network functions. With the development of Internet and the emergence of software-defined networking (SDN), the methods designed for the traditional 5-dimensional rule set is not sufficient to process the current rule set that contains rules of 12 or more dimensions. The main problem is to process the rule sets of 12 or more dimensions in high throughput. To achieve high throughput, we study the implementations on GPU where some use a single hash table and others use Binary Range Tree to process the searching. In 12-dimensional rule sets defined by OpenFlow 1.0, 8 fields are in the format of exact value or wildcard, and so using the single hash table or binary range tree is not efficient. Another problem to implement packet classification on GPU is that we must transfer the input data and results via the PCI-E bus that will incur long bus latency. In this paper, we propose a modified hash table to process the fields that contain only exact value or wildcard, and use the compressing method to reduce memory consumption. On the other hand, we implement the proposed method on APU that uses Heterogeneous System Architecture to skip the bus latency. According to the experimental results on AMD A10–7850 APU, our method can achieve the throughput of 1814 MPPS, and can support the rule sets of more than 12K 12-dimensional rules. The achieved throughput is 10 times of the methods on legacy GPU. more...
- Published
- 2019
- Full Text
- View/download PDF
21. Approximation of smallest linear tree grammar
- Author
-
Artur Jeź and Markus Lohrey
- Subjects
FOS: Computer and information sciences ,K-ary tree ,Formal Languages and Automata Theory (cs.FL) ,E.4 ,Computer Science - Formal Languages and Automata Theory ,0102 computer and information sciences ,02 engineering and technology ,Exponential tree ,Interval tree ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Data Structures and Algorithms (cs.DS) ,Mathematics ,Discrete mathematics ,000 Computer science, knowledge, general works ,Spanning tree ,Segment tree ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Computer Science Applications ,Range tree ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Computer Science ,F.4.2 ,020201 artificial intelligence & image processing ,Gomory–Hu tree ,F.2.2 ,Computer Science::Formal Languages and Automata Theory ,Order statistic tree ,Information Systems - Abstract
A simple linear-time algorithm for constructing a linear context-free tree grammar of size O(rg + r g log (n/r g))for a given input tree T of size n is presented, where g is the size of a minimal linear context-free tree grammar for T, and r is the maximal rank of symbols in T (which is a constant in many applications). This is the first example of a grammar-based tree compression algorithm with a good, i.e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees., Comment: 45 pages, published in Information and Computation. Approximation ratio improved since the first version, figures improved, some examples added. A small calculation error corrected since the previous version (all claims hold as previously) more...
- Published
- 2016
- Full Text
- View/download PDF
22. On approximating tree spanners that are breadth first search trees
- Author
-
Ioannis Papoutsakis
- Subjects
FOS: Computer and information sciences ,K-ary tree ,Computer Networks and Communications ,0102 computer and information sciences ,Exponential tree ,Computational Complexity (cs.CC) ,Computer Science::Computational Geometry ,Minimum spanning tree ,k-minimum spanning tree ,Interval tree ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,0101 mathematics ,Computer Science::Data Structures and Algorithms ,Mathematics ,Discrete mathematics ,Spanning tree ,Applied Mathematics ,010102 general mathematics ,Range tree ,Computer Science - Computational Complexity ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Gomory–Hu tree ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
A tree $t$-spanner $T$ of a graph $G$ is a spanning tree of $G$ such that the distance in $T$ between every pair of verices is at most $t$ times the distance in $G$ between them. There are efficient algorithms that find a tree $t\cdot O(\log n)$-spanner of a graph $G$, when $G$ admits a tree $t$-spanner. In this paper, the search space is narrowed to $v$-concentrated spanning trees, a simple family that includes all the breadth first search trees starting from vertex $v$. In this case, it is not easy to find approximate tree spanners within factor almost $o(\log n)$. Specifically, let $m$ and $t$ be integers, such that $m>0$ and $t\geq 7$. If there is an efficient algorithm that receives as input a graph $G$ and a vertex $v$ and returns a $v$-concentrated tree $t\cdot o((\log n)^{m/(m+1)})$-spanner of $G$, when $G$ admits a $v$-concentrated tree $t$-spanner, then there is an algorithm that decides 3-SAT in quasi-polynomial time. more...
- Published
- 2016
- Full Text
- View/download PDF
23. The ℵ 0-categorical Trees
- Author
-
Robert Barham
- Subjects
Discrete mathematics ,Algebra and Number Theory ,K-ary tree ,Link/cut tree ,Ramification (botany) ,010102 general mathematics ,Weight-balanced tree ,0102 computer and information sciences ,01 natural sciences ,Search tree ,Range tree ,Combinatorics ,Tree structure ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Metric tree ,Geometry and Topology ,0101 mathematics ,Mathematics - Abstract
We provide a description of the structure of ℵ 0-categorical trees. First the maximal branches of ℵ 0-categorical tree are examined, followed by the configuration of the ramification orders, which are then combined to provided necessary and sufficient conditions for a tree to be ℵ 0-categorical in terms of these two things. more...
- Published
- 2016
- Full Text
- View/download PDF
24. Distributions of topological tree metrics between a species tree and a gene tree
- Author
-
Jing Xi, Ruriko Yoshida, and Jin Xie
- Subjects
0301 basic medicine ,Statistics and Probability ,Discrete mathematics ,K-ary tree ,0206 medical engineering ,Populations and Evolution (q-bio.PE) ,02 engineering and technology ,Interval tree ,Topology ,Search tree ,Random binary tree ,Range tree ,Combinatorics ,03 medical and health sciences ,030104 developmental biology ,Tree structure ,FOS: Biological sciences ,Tree rearrangement ,Quantitative Biology - Populations and Evolution ,020602 bioinformatics ,Tree measurement ,Mathematics - Abstract
In order to conduct a statistical analysis on a given set of phylogenetic gene trees, we often use a distance measure between two trees. In a statistical distance-based method to analyze discordance between gene trees, it is a key to decide "biological meaningful" and "statistically well-distributed" distance between trees. Thus, in this paper, we study the distributions of the three tree distance metrics: the edge difference, the path difference, and the precise $K$ interval cospeciation distance, between two trees: first, we focus on distributions of the three tree distances between two random unrooted trees with $n$ leaves ($n \geq 4$); and then we focus on the distributions the three tree distances between a fixed rooted species tree with $n$ leaves and a random gene tree with $n$ leaves generated under the coalescent process with given the species tree. We show some theoretical results as well as simulation study on these distributions., 18 pages, 11 figures more...
- Published
- 2016
- Full Text
- View/download PDF
25. Tree edit distance: Robust and memory-efficient
- Author
-
Mateusz Pawlik and Nikolaus Augsten
- Subjects
Fractal tree index ,Tree rotation ,Theoretical computer science ,K-ary tree ,Computer science ,Nearest neighbor search ,Segment tree ,02 engineering and technology ,Wagner–Fischer algorithm ,Interval tree ,Search tree ,Range tree ,Hardware and Architecture ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Edit distance ,Algorithm ,Software ,Information Systems - Abstract
Hierarchical data are often modelled as trees. An interesting query identifies pairs of similar trees. The standard approach to tree similarity is the tree edit distance, which has successfully been applied in a wide range of applications. In terms of runtime, the state-of-the-art algorithm for the tree edit distance is RTED, which is guaranteed to be fast independent of the tree shape. Unfortunately, this algorithm requires up to twice the memory of its competitors. The memory is quadratic in the tree size and is a bottleneck for the tree edit distance computation.In this paper we present a new, memory efficient algorithm for the tree edit distance, AP-TED (All Path Tree Edit Distance). Our algorithm runs at least as fast as RTED without trading in memory efficiency. This is achieved by releasing memory early during the first step of the algorithm, which computes a decomposition strategy for the actual distance computation. We show the correctness of our approach and prove an upper bound for the memory usage. The strategy computed by AP-TED is optimal in the class of all-path strategies, which subsumes the class of LRH strategies used in RTED. We further present the AP-TED+ algorithm, which requires less computational effort for very small subtrees and improves the runtime of the distance computation. Our experimental evaluation confirms the low memory requirements and the runtime efficiency of our approach. HighlightsWe address the memory problem of the strategy computation in the RTED algorithm for the tree edit distance.We prove an upper bound which guarantees that the strategy computation never uses more memory than the distance computation.We compute the optimal strategy in the class of all-path strategies which subsumes the LRH strategies used before.We develop new single-path functions which are better in terms of runtime and memory than the previously used functions. more...
- Published
- 2016
- Full Text
- View/download PDF
26. Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors.
- Author
-
Wee, Y., Chaiken, S., and Ravi, S.
- Abstract
We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set of n points in the plane. For this problem, we introduce a variation of a subgraph of size O(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] from O(n log n) to O( n log n). The second problem is the construction of a rectilinear minimum spanning tree for a set of n noncrossing line segments in the plane. We present an optimal O( n log n) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons. [ABSTRACT FROM AUTHOR] more...
- Published
- 1994
- Full Text
- View/download PDF
27. Output-sensitive generation of the perspective view of isothetic parallelepipeds.
- Author
-
Preparata, Franco, Vitter, Jeffrey, and Yvinec, Mariette
- Abstract
We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses 0(( n + d) log n log log n) time, where n is the number of 3D-rectangles and d is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries in O((log n + k) log log n) time, where k is the size of the response, and insertions and deletions in O(log n log log n) time, all in the worst case. [ABSTRACT FROM AUTHOR] more...
- Published
- 1992
- Full Text
- View/download PDF
28. Computing on a free tree via complexity-preserving mappings.
- Author
-
Chazelle, Bernard
- Abstract
The relationship between linear lists and free trees is studied. We examine a number of well-known data structures for computing functions on linear lists and show that they can be canonically transformed into data structures for computing the same functions defined over free trees. This is used to establish new upper bounds on the complexity of several query-answering problems. [ABSTRACT FROM AUTHOR] more...
- Published
- 1987
- Full Text
- View/download PDF
29. Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
- Author
-
Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
- Subjects
FOS: Computer and information sciences ,Delaunay triangulation ,Computer science ,Parallel algorithm ,0102 computer and information sciences ,02 engineering and technology ,Parallel computing ,Data structure ,Interval tree ,01 natural sciences ,Range tree ,Non-volatile memory ,k-d tree ,010201 computation theory & mathematics ,020204 information systems ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Data Structures and Algorithms (cs.DS) ,Standard algorithms - Abstract
In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, $k$-d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-Parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are $\omega$ times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, reconstruction-based rebalancing and $\alpha$-labeling, which we believe will be useful for designing other parallel write-efficient algorithms. more...
- Published
- 2018
- Full Text
- View/download PDF
30. Mobile Location Based Indexing for Range Searching
- Author
-
Sabai Phyu and Thu Thu Zan
- Subjects
Computer science ,Dynamic data ,Search engine indexing ,020302 automobile design & engineering ,02 engineering and technology ,computer.software_genre ,Object (computer science) ,Range tree ,Range searching ,k-d tree ,Tree (data structure) ,0203 mechanical engineering ,Data mining ,computer - Abstract
There had been numerous uses based on two dimensional indexing techniques in recent years. Such uses were generally intended to static data or no moving object data. Today indexing is essential for both static and dynamic data with advances in location services. It is not difficult to store and process for both of them but it need to be consistent for update between arbitrary and unpredictable number of moving object nodes and index structure. For this reason, this paper proposed moving object index structure based on presort range tree that will store moving locations conveniently. In this case, synthetic dataset is needed to generate accessing for several of moving location data. Therefore, this paper also proposed a procedure to generate a synthetic dataset that is the creation of dynamic two dimensional points. Besides, there is a comparison between different indexing techniques such as presort range tree and kd tree along with performance evaluation of tree construction and range searching over moving objects. Moreover, distance based range searching is added to compare between two of indexing. more...
- Published
- 2018
- Full Text
- View/download PDF
31. Certain height-balanced subtrees of hypercubes
- Author
-
Indhumathi Raman
- Subjects
Combinatorics ,Discrete mathematics ,Computational Mathematics ,AVL tree ,K-ary tree ,Computational Theory and Mathematics ,Segment tree ,2–3 tree ,Interval tree ,Search tree ,Left-child right-sibling binary tree ,Range tree ,Mathematics - Abstract
A height-balanced tree is a desired data structure for performing operations such as search, insert and delete, on high-dimensional external data storage. Its preference is due to the fact that it always maintains logarithmic height even in worst cases. It is a rooted binary tree in which for every vertex the difference (denoted as balance factor) in the heights of the subtrees, rooted at the left and the right child of the vertex, is at most one. In this paper, we consider two subclasses of height-balanced trees and . A tree in is such that all the vertices up to (a predetermined) level t has balance factor one and the remaining vertices have balance factor zero. A tree in is such that all the vertices at alternate levels up to t has balance factor one and the remaining vertices have balance factor zero. We prove that every tree in the classes and is a subtree of the hypercube. more...
- Published
- 2016
- Full Text
- View/download PDF
32. A navigation system for tree space
- Author
-
Sarah Mark, Mike Steel, and Jeanette C. McLeod
- Subjects
0301 basic medicine ,Discrete mathematics ,K-ary tree ,General Computer Science ,Interval tree ,Search tree ,Computer Science Applications ,Theoretical Computer Science ,Range tree ,Combinatorics ,03 medical and health sciences ,030104 developmental biology ,Tree structure ,Computational Theory and Mathematics ,Tree rearrangement ,Geometry and Topology ,Left-child right-sibling binary tree ,Vantage-point tree ,Mathematics - Abstract
The reconstruction of evolutionary trees from data sets on overlapping sets of species is a central problem in phylogenetics. Provided that the tree reconstructed for each subset of species is rooted and that these trees t together consistently, the space of all parent trees that ‘display’ these trees was recently shown to satisfy the following strong property: there exists a path from any one parent tree to any other parent tree by a sequence of local rearrangements (nearest neighbour interchanges) so that each intermediate tree also lies in this same tree space. However, the proof of this result uses a non-constructive argument. In this paper we describe a specic, polynomial-time procedure for navigating from any given parent tree to another while remaining in this tree space. The results are of particular relevance to the recent study of ‘phylogenetic terraces’. more...
- Published
- 2016
- Full Text
- View/download PDF
33. Similar Subtree Search Using Extended Tree Inclusion
- Author
-
Atsuhiro Takasu, Jaewook Hwang, Jesper Jansson, Tatsuya Akutsu, Takeyuki Tamura, and Tomoya Mori
- Subjects
Discrete mathematics ,Incremental decision tree ,Theoretical computer science ,AVL tree ,K-ary tree ,Computer science ,Segment tree ,0102 computer and information sciences ,Interval tree ,01 natural sciences ,Search tree ,Computer Science Applications ,Range tree ,Combinatorics ,Tree (data structure) ,(a,b)-tree ,Tree structure ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Time complexity ,Information Systems ,Mathematics - Abstract
This paper considers the problem of identifying all locations of subtrees in a large tree or in a large collection of trees that are similar to a specified pattern tree, where all trees are assumed to be rooted and node-labeled. The tree edit distance is a widely-used measure of tree (dis-)similarity, but is NP-hard to compute for unordered trees. To cope with this issue, we propose a new similarity measure which extends the concept of unordered tree inclusion by taking the costs of insertion and substitution operations on the pattern tree into account, and present an algorithm for computing it. Our algorithm has the same time complexity as the original one for unordered tree inclusion, i.e., it runs in $O(|T_1||T_2|)$ time, where $T_1$ and $T_2$ denote the pattern tree and the text tree, respectively, when the maximum outdegree of $T_1$ is bounded by a constant. Our experimental evaluation using synthetic and real datasets confirms that the proposed algorithm is fast and scalable and very useful for bibliographic matching, which is a typical entity resolution problem for tree-structured data. Furthermore, we extend our algorithm to also allow a constant number of deletion operations on $T_1$ while still running in $O(|T_1||T_2|)$ time. more...
- Published
- 2015
- Full Text
- View/download PDF
34. Three Steps Strategy to Search for Optimum Classification Trees
- Author
-
Muhammad Aslam, Karl P. Pfeiffer, and Muhammad Azam
- Subjects
Statistics and Probability ,Decision tree learning ,05 social sciences ,computer.software_genre ,Interval tree ,01 natural sciences ,Search tree ,Range tree ,010104 statistics & probability ,Tree traversal ,Modeling and Simulation ,0502 economics and business ,Ternary search tree ,Exponent ,Entropy (information theory) ,Data mining ,0101 mathematics ,computer ,050205 econometrics ,Mathematics - Abstract
This article presents a new strategy to construct classification trees. According to the proposed scheme, we focused on keeping the record of sequences of each constructed classification tree; both in terms of splitting predictors and their splitting values in an array. So overall we have as many arrays as we have drawn samples. At this stage, a three steps strategy is introduced, which is used to search for the optimum classification tree. The proposed strategy provides comparable or improved results in terms of generalized error rates than tree and rpart (packages available for classification purposes in the R) using four of the well-known evaluation functions, that is, the Gini, the Entropy, the Twoing, and the Exponent-based function to split nodes for many real-life datasets. more...
- Published
- 2015
- Full Text
- View/download PDF
35. On the hardness of full Steiner tree problems
- Author
-
Michiel Smid, Ahmad Biniaz, and Anil Maheshwari
- Subjects
Tree rotation ,Discrete mathematics ,AVL tree ,K-ary tree ,010102 general mathematics ,TheoryofComputation_GENERAL ,0102 computer and information sciences ,Minimum spanning tree ,k-minimum spanning tree ,01 natural sciences ,Steiner tree problem ,Theoretical Computer Science ,Range tree ,Combinatorics ,symbols.namesake ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Hardware_INTEGRATEDCIRCUITS ,symbols ,Discrete Mathematics and Combinatorics ,Gomory–Hu tree ,0101 mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Given a weighted graph G = ( V , E ) and a subset R of V, a Steiner tree in G is a tree which spans all vertices in R. The vertices in V ? R are called Steiner vertices. A full Steiner tree is a Steiner tree in which each vertex of R is a leaf. The full Steiner tree problem is to find a full Steiner tree with minimum weight. The bottleneck full Steiner tree problem is to find a full Steiner tree which minimizes the length of the longest edge. The k-bottleneck full Steiner tree problem is to find a bottleneck full Steiner tree with at most k Steiner vertices. The smallest full Steiner tree problem is to find a full Steiner tree with the minimum number of Steiner vertices.We show that the full Steiner tree problem in general graphs cannot be approximated within a factor of O ( log 2 - e ? | R | ) for any e 0 . We also provide a polynomial-time approximation factor preserving reduction from the full Steiner tree problem to the group Steiner tree problem. Based on that, the first approximation algorithm for the full Steiner tree problem in general graphs is obtained. Moreover, we show that the same hardness result holds for the node-weighted version of the full Steiner tree problem. We prove that it is NP-hard to approximate the k-bottleneck full Steiner tree problem within a factor of 2 - e . The smallest full Steiner tree problem is shown to be NP-complete and does not admit any polynomial-time O ( ( 1 - e ) ln ? n ) -approximation algorithm. The presented reductions show the connection between the full Steiner tree, the group Steiner tree, and the connected set cover problems. In addition, we present an O ( | E | log ? | V | ) time algorithm for the bottleneck full Steiner tree problem which relaxes the assumption, that G is a complete graph, in Chen et al. 7 algorithm. more...
- Published
- 2015
- Full Text
- View/download PDF
36. Multi-pipelined and memory-efficient packet classification engines on FPGAs
- Author
-
Aydin Carus and Oguzhan Erdem
- Subjects
Computer Networks and Communications ,Computer science ,Backtracking ,Network packet ,Pipeline (computing) ,Trie ,Linked list ,Parallel computing ,Data structure ,Range tree - Abstract
A packet classification task incorporated in network firewalls to recognize and sift threats or unauthorized network accesses is accomplished by checking incoming packet headers against a pre-defined filter set. Plenty of solutions to reduce the memory requirement of filter set storage and accommodate packet classification to line rates have been proposed over the past decade. Among all the existing approaches, hierarchical data structures maintain great memory performance however their hardware realization suffers from two issues: (i) backtracking and (ii) memory inefficiency. In this paper, we propose two data structures denoted range tree-linked list hierarchical search structure (RLHS) and value-coded trie structure with -branch property (VC) for packet classification. RLHS resolves backtracking by exploiting range tree in Stage 1 and linked list data structure in Stage 2 overcomes the memory inefficiency. VC trie that naturally does not involve backtracking problem, solves memory inefficiency issue by comprising a fixed size bin at each node. Apart from conventional binary trie, a new rule is inserted into the first available bin on the path of this rule in a VC trie, and -branch property is utilized in case all the bins are full. We also propose a rule categorization algorithm that partitions an input ruleset by considering the field features of rules to minimize the memory requirement. To support the proposed data structures, we designed high throughput SRAM-based parallel and pipelined architectures on Field Programmable Gate Arrays (FPGAs). more...
- Published
- 2015
- Full Text
- View/download PDF
37. Group nearest-neighbor queries in the L1 plane
- Author
-
Hee-Kap Ahn, Wanbin Son, and Sang Won Bae
- Subjects
Discrete mathematics ,General Computer Science ,Group (mathematics) ,Generalization ,Data structure ,Theoretical Computer Science ,Sweep line algorithm ,k-nearest neighbors algorithm ,Range tree ,Combinatorics ,Set (abstract data type) ,Integer ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Mathematics - Abstract
Let P be a set of n points in the plane. The k-nearest-neighbor (abbreviated as k-NN) query problem is to preprocess P into a data structure that quickly reports k closest points in P for a query point q. This paper addresses a generalization of the k-NN query problem to a query set Q of points, namely, the group k-nearest-neighbor query problem, in the L 1 plane. More precisely, a query is assigned with a set Q of at most m points and a positive integer k with k ? n , and the distance between a point p of P and a query set Q is defined as the sum of L 1 distances from p to all q ? Q . The maximum number m of query points Q is assumed to be known in advance and to be at most n. In this paper, we propose two algorithms, one based on the range tree and the other based on a data structure for segment dragging queries, and obtain the following complexity bounds: (1) a group k-NN query can be handled in O ( T min log ? n + ( k + m 2 ) ( log ? log ? n + log ? m ) ) time after preprocessing P using O ( m 2 n log 2 ? n ) space, where T min = min ? { k + m , m 2 } , or (2) a group k-NN query can be handled in O ( ( k + m ) log 2 ? n + m 2 ( log ? ? n + log ? m ) ) time after preprocessing P using O ( m 2 n ) space, where ? 0 is an arbitrarily small constant. We also show that our approach can be applied to the weighted group k-nearest-neighbor query problem and the group k-farthest-neighbor query problem. more...
- Published
- 2015
- Full Text
- View/download PDF
38. On full Steiner trees in unit disk graphs
- Author
-
Ahmad Biniaz, Michiel Smid, and Anil Maheshwari
- Subjects
Control and Optimization ,K-ary tree ,0102 computer and information sciences ,Minimum spanning tree ,k-minimum spanning tree ,01 natural sciences ,Steiner tree problem ,Combinatorics ,03 medical and health sciences ,symbols.namesake ,0302 clinical medicine ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Mathematics ,Discrete mathematics ,Spanning tree ,Shortest-path tree ,Computer Science Applications ,Range tree ,Computational Mathematics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,030220 oncology & carcinogenesis ,symbols ,Gomory–Hu tree ,Geometry and Topology ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Given an edge-weighted graph G = ( V , E ) and a subset R of V, a Steiner tree of G is a tree which spans all the vertices in R. A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G. As for λ-precise unit disk graphs we present a ( 10 + 1 λ ) -approximation algorithm, where λ is the length of the shortest edge in G. more...
- Published
- 2015
- Full Text
- View/download PDF
39. Efficient Computation of the Tree Edit Distance
- Author
-
Nikolaus Augsten and Mateusz Pawlik
- Subjects
Tree (data structure) ,K-ary tree ,Computer science ,Segment tree ,Edit distance ,Wagner–Fischer algorithm ,Interval tree ,Algorithm ,Search tree ,Information Systems ,Range tree - Abstract
We consider the classical tree edit distance between ordered labelled trees, which is defined as the minimum-cost sequence of node edit operations that transform one tree into another. The state-of-the-art solutions for the tree edit distance are not satisfactory. The main competitors in the field either have optimal worst-case complexity but the worst case happens frequently, or they are very efficient for some tree shapes but degenerate for others. This leads to unpredictable and often infeasible runtimes. There is no obvious way to choose between the algorithms. In this article we present RTED, a robust tree edit distance algorithm. The asymptotic complexity of our algorithm is smaller than or equal to the complexity of the best competitors for any input instance, that is, our algorithm is both efficient and worst-case optimal. This is achieved by computing a dynamic decomposition strategy that depends on the input trees. RTED is shown optimal among all algorithms that use LRH ( left-right-heavy ) strategies, which include RTED and the fastest tree edit distance algorithms presented in literature. In our experiments on synthetic and real-world data we empirically evaluate our solution and compare it to the state-of-the-art. more...
- Published
- 2015
- Full Text
- View/download PDF
40. Vizualizace evoluce algoritmů datových struktur uchovávajících bodová multidimenzionální data
- Author
-
Kavička, Antonín, Fikejz, Jan, Samek, Miloš, Kavička, Antonín, Fikejz, Jan, and Samek, Miloš
- Abstract
Diplomová práce se zabývá tématem vizualizace datových struktur uchovávající multidimenzionální bodová data a jejich operací. Konkrétně se jedná o vizualizace prioritního vyhledávacího stromu, rozsahového stromu a dvou typů quad stromu. Sekundárním cílem bylo zpracování vizualizací lineárních průchodů prostorem, a to Peanovy křivky, Hilbertovy křivky a Z-křivky., The primary topic of this thesis is visualization of data structures used to store multidimensional point data and their operations. Specifically, this thesis covers visualisations of the priority search tree, range tree and two quad tree specifications. The secondary goal was to create visualisations of linear orderings of Peano curve, Hilbert curve and Z-curve., Fakulta elektrotechniky a informatiky, Diplomová práce navrhuje a implementuje webovou aplikaci pro vizualizaci evoluce algoritmů vybraných datových struktur. V práci je využito především znalostí z datových struktur, pokročilých programovacích technik, a databází. Jako softwarový prostředek pro implementaci byla zvolena platforma Srping boot, Vaadin a Hibernate. V praktické části se student věnuje vlastnímu návrhu a implementaci webové aplikace pro vizualizaci evoluce algoritmů datových struktur, které byly představeny v teoretické části práce. V rámci implementace je navrženo jednoduché uživatelské rozhraní pro vizualizaci klíčových operací. Vlastní implementace vybraných datových struktur vychází z navrženého jednotného rozhraní a využívá generické datové typy. Diplomová práce podle systému IS STAG nevykazuje známky plagiátorství. more...
- Published
- 2018
41. Approximation Algorithms for Multiple Sequence Alignment under a Fixed Evolutionary Tree
- Author
-
R. Ravi and John Kececioglu
- Subjects
Discrete mathematics ,150399 Business and Management not elsewhere classified ,K-ary tree ,Multiple sequence alignment ,Phylogenetic tree ,Applied Mathematics ,k-minimum spanning tree ,Steiner tree problem ,Tree (graph theory) ,Approximation algorithms ,Range tree ,Combinatorics ,Computational biology ,FOS: Economics and business ,symbols.namesake ,symbols ,Discrete Mathematics and Combinatorics ,Evolutionary trees ,Time complexity ,Mathematics - Abstract
We consider the problem of multiple sequence alignment under a fixed evolutionary tree: given a tree whose leaves are labeled by sequences, find ancestral sequences to label its internal nodes so as to minimize the total length of the tree, where the length of an edge is the edit distance between the sequences labeling its endpoints. We present a new polynomial-time approximation algorithm for this problem, and analyze its performance on regular d-ary trees with d a constant. On such a tree, the algorithm finds a solution within a factor (d + 1)/(d − 1) of the minimum in O(kdT(d, n) + k2dn2) time, where k is the number of leaves in the tree, n is the length of the longest sequence labeling a leaf, and T(d, n) is the time to compute a Steiner point for d sequences of length at most n. (A Steiner point for a set S of sequences is a sequence P that minimizes the sum of the edit distances from P to each sequence in S . The time T(d, n) is O(d2dnd), given O(dsd+1)-time preprocessing for an alphabet of size s.) The approximation algorithm is conceptually simple and easy to implement, and actually applies to any metric space in which a Steiner point for any fixed-sized set can be computed in polynomial time. We also introduce a new problem, bottleneck tree-alignment, in which the objective is to label the internal nodes of the tree so as to minimize the length of the longest edge. We describe an exponential-time exact algorithm for the case of unit-cost edit operations, and show there is a simple linear-time approximation algorithm for the general case that finds a solution within a factor O(logk) of the minimum. more...
- Published
- 2018
- Full Text
- View/download PDF
42. Efficient Genomic Interval Queries Using Augmented Range Trees
- Author
-
Alal Eran, Chengsheng Mao, and Yuan Luo
- Subjects
0301 basic medicine ,FOS: Computer and information sciences ,Theoretical computer science ,Range query (data structures) ,Computer science ,Science ,Fractional cascading ,Interval tree ,Quantitative Biology - Quantitative Methods ,Article ,03 medical and health sciences ,0302 clinical medicine ,Computer Science - Databases ,Computer Science - Data Structures and Algorithms ,Humans ,Data Structures and Algorithms (cs.DS) ,Time complexity ,Quantitative Methods (q-bio.QM) ,Multidisciplinary ,Computational Biology ,Databases (cs.DB) ,Genomics ,Data structure ,Range tree ,030104 developmental biology ,FOS: Biological sciences ,Interval (graph theory) ,Medicine ,Rewriting ,Algorithms ,Software ,030217 neurology & neurosurgery - Abstract
Efficient large-scale annotation of genomic intervals is essential for personal genome interpretation in the realm of precision medicine. There are 13 possible relations between two intervals according to Allen's interval algebra. Conventional interval trees are routinely used to identify the genomic intervals satisfying a coarse relation with a query interval, but cannot support efficient query for more refined relations such as all Allen's relations. We design and implement a novel approach to address this unmet need. Through rewriting Allen's interval relations, we transform an interval query to a range query, then adapt and utilize the range trees for querying. We implement two types of range trees: a basic 2-dimensional range tree (2D-RT) and an augmented range tree with fractional cascading (RTFC) and compare them with the conventional interval tree (IT). Theoretical analysis shows that RTFC can achieve the best time complexity for interval queries regarding all Allen's relations among the three trees. We also perform comparative experiments on the efficiency of RTFC, 2D-RT and IT in querying noncoding element annotations in a large collection of personal genomes. Our experimental results show that 2D-RT is more efficient than IT for interval queries regarding most of Allen's relations, RTFC is even more efficient than 2D-RT. The results demonstrate that RTFC is an efficient data structure for querying large-scale datasets regarding Allen's relations between genomic intervals, such as those required by interpreting genome-wide variation in large populations., Comment: 4 figures, 4 tables more...
- Published
- 2018
- Full Text
- View/download PDF
43. Spherical Region Queries on Multicore Architectures
- Author
-
Hao Lu, Wei Guo, Sudip K. Seal, and John Poplawsky
- Subjects
Multi-core processor ,Speedup ,Scale (descriptive set theory) ,02 engineering and technology ,Parallel computing ,010402 general chemistry ,021001 nanoscience & nanotechnology ,01 natural sciences ,0104 chemical sciences ,Range tree ,Tree (data structure) ,k-d tree ,Naive algorithm ,Data analysis ,0210 nano-technology - Abstract
In this short paper, we report the performance of multiple thread-parallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms. more...
- Published
- 2017
- Full Text
- View/download PDF
44. Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif
- Author
-
Maurice Pouzet, Claude Laflamme, Norbert Sauer, University of Calgary, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Combinatoire, théorie des nombres (CTN), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL) more...
- Subjects
Discrete mathematics ,K-ary tree ,General Mathematics ,010102 general mathematics ,Weight-balanced tree ,0102 computer and information sciences ,Scapegoat tree ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Interval tree ,01 natural sciences ,Random binary tree ,Range tree ,Combinatorics ,010201 computation theory & mathematics ,Metric tree ,0101 mathematics ,2–3 tree ,ComputingMilieux_MISCELLANEOUS ,Mathematics - Abstract
A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees. more...
- Published
- 2017
- Full Text
- View/download PDF
45. Non-Depth-First Search against Independent Distributions on an AND-OR Tree
- Author
-
Toshio Suzuki
- Subjects
FOS: Computer and information sciences ,K-ary tree ,Computer Science - Artificial Intelligence ,Breadth-first search ,0102 computer and information sciences ,Interval tree ,01 natural sciences ,Random binary tree ,Theoretical Computer Science ,Combinatorics ,68T20, 68W40 ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,0101 mathematics ,Mathematics ,010102 general mathematics ,I.2.8 ,F.2.2 ,Computer Science Applications ,Range tree ,Tree traversal ,Artificial Intelligence (cs.AI) ,010201 computation theory & mathematics ,Signal Processing ,Tree (set theory) ,Order statistic tree ,Information Systems - Abstract
Suzuki and Niida (Ann. Pure. Appl. Logic, 2015) showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into consideration. (1) Among IDs such that probability of the root having value 0 is fixed as a given r such that 0 < r < 1, if d is a maximizer of cost of the best algorithm then d is an independent and identical distribution (IID). (2) Among all IDs, if d is a maximizer of cost of the best algorithm then d is an IID. In the case where non-depth-first algorithms are taken into consideration, the counter parts of (1) and (2) are left open in the above work. Peng et al. (Inform. Process. Lett., 2017) extended (1) and (2) to multi-branching trees, where in (2) they put an additional hypothesis on IDs that probability of the root having value 0 is neither 0 nor 1. We give positive answers for the two questions of Suzuki-Niida. A key to the proof is that if ID d achieves the equilibrium among IDs then we can chose an algorithm of the best cost against d from depth-first algorithms. In addition, we extend the result of Peng et al. to the case where non-depth-first algorithms are taken into consideration., 12 pages, 1 figure more...
- Published
- 2017
46. Improved Bounds on Absolute Positiveness of Multivariate Polynomials
- Author
-
Vikram Sharma and Swaroop N. Prabhakar
- Subjects
Polynomial ,Sequence ,Algebra and Number Theory ,Generalization ,010102 general mathematics ,Univariate ,010103 numerical & computational mathematics ,02 engineering and technology ,Absolute value (algebra) ,01 natural sciences ,Upper and lower bounds ,Range tree ,Combinatorics ,Computational Mathematics ,Range (mathematics) ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,0202 electrical engineering, electronic engineering, information engineering ,Partial derivative ,020201 artificial intelligence & image processing ,Chapman–Robbins bound ,0101 mathematics ,Mathematics ,Real number - Abstract
A multivariate polynomial F ( x 1 , x 2 , … , x n ) is said to be absolutely positive from a real number B if F and all its partial derivatives are non-negative for x 1 , x 2 , … , x n ≥ B . One of the well known bounds on absolute positiveness in the literature is due to Hong. His bound is dependent on the largest number in a certain sequence of radicals defined using the absolute value of the coefficients of the polynomial. In the univariate setting, a bound due to Lagrange considers the first and the second largest numbers in the same radical sequence and is shown by Collins to be better than Hong's bound. In the 1930's, Westerfield had proposed a bound that considers every value in the same radical sequence and improves on Lagrange's bound. In this paper, we provide a hierarchy of bounds generalizing Westerfield's bound to the multivariate setting. One of the bounds in this hierarchy is a generalization of Lagrange's bound. All the bounds are strict quantitative improvements over Hong's bound. We also give an algorithm to compute the multivariate Lagrange bound. The running time of this algorithm matches the running time of the best known algorithm to compute Hong's bound. The algorithm uses the range tree data structure to implement orthogonal range querying. Relying on a result of Fredman (1984), we show that the efficiency of this algorithm cannot be improved by using any other data structure for orthogonal range querying. more...
- Published
- 2017
- Full Text
- View/download PDF
47. BEST LOOKUP ALGORITHM FOR 100+GBPS IPV6 PACKET FORWARDING
- Author
-
Sangeetha Jose and Suja G J
- Subjects
computer.internet_protocol ,Computer science ,business.industry ,Network packet ,Distributed computing ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Internet traffic ,IPv4 ,Range tree ,IPv6 ,IPv6 packet ,Key (cryptography) ,Distributed memory ,business ,computer ,Algorithm ,Computer network - Abstract
As internet traffic is growing day by day, it is a key requirement to increase more and more IP addresses. IPv4 cannot accommodate this need due to the exhaustion of its 2 32 address. Hence in order to effectively satisfies this increase in demand for IP address new addressing scheme called IPv6 is developed. It has 2 128 addresses so the exhaustion is not possible in near future. To forward IPv4 packet efficient mechanisms are there. But IPv6 is of 128bit length, so the present forwarding techniques is not possible to forward IPv6 packet effectively. In this paper we try to explore currently existing different lookup algorithms (Distributed Memory Organizations, Triec, Recursive Balanced Multi-way range trees and Range tree based IPv6 lookup) and analyze the best lookup algorithm for 100+ Gbps IPv6 packet forwarding by performing a comparative survey. more...
- Published
- 2014
- Full Text
- View/download PDF
48. Radio Numbers of Certain m-Distant Trees
- Author
-
Pratima Panigrahi and Srinivasa Rao Kola
- Subjects
Discrete mathematics ,Combinatorics ,K-ary tree ,Integer ,Shortest-path tree ,Distance ,Graph ,Vertex (geometry) ,Range tree ,Mathematics - Abstract
Radio coloring of a graph G with diameter d is an assignment f of positive integers to the vertices of G such that |f(u)-f(v)|≥1+d-d(u,v), where u and v are any two distinct vertices of G and d(u,v) is the distance between u and v. The number max {f(u):u∈V(G)} is called the span of f. The minimum of spans over all radio colorings of G is called radio number of G, denoted by rn(G). An m-distant tree T is a tree in which there is a path P of maximum length such that every vertex in V(T)∖V(P) is at the most distance m from P. This path P is called a central path. For every tree T, there is an integer m such that T is a m-distant tree. In this paper, we determine the radio number of some m-distant trees for any positive integer m≥2, and as a consequence of it, we find the radio number of a class of 1-distant trees (or caterpillars). more...
- Published
- 2014
- Full Text
- View/download PDF
49. Neighborhoods of Trees in Circular Orderings
- Author
-
Sarah, Bastkowski, Sarah, Baskowski, Vincent, Moulton, Andreas, Spillner, and Taoyang, Wu
- Subjects
Pharmacology ,Discrete mathematics ,Likelihood Functions ,Binary tree ,K-ary tree ,Models, Genetic ,General Mathematics ,General Neuroscience ,Immunology ,Weight-balanced tree ,Mathematical Concepts ,Interval tree ,General Biochemistry, Genetics and Molecular Biology ,Random binary tree ,Range tree ,Evolution, Molecular ,Combinatorics ,Tree traversal ,Computational Theory and Mathematics ,Tree rearrangement ,General Agricultural and Biological Sciences ,Algorithms ,Phylogeny ,General Environmental Science ,Mathematics - Abstract
In phylogenetics, a common strategy used to construct an evolutionary tree for a set of species $$X$$ is to search in the space of all such trees for one that optimizes some given score function (such as the minimum evolution, parsimony or likelihood score). As this can be computationally intensive, it was recently proposed to restrict such searches to the set of all those trees that are compatible with some circular ordering of the set $$X$$ . To inform the design of efficient algorithms to perform such searches, it is therefore of interest to find bounds for the number of trees compatible with a fixed ordering in the neighborhood of a tree that is determined by certain tree operations commonly used to search for trees: the nearest neighbor interchange (nni), the subtree prune and regraft (spr) and the tree bisection and reconnection (tbr) operations. We show that the size of such a neighborhood of a binary tree associated with the nni operation is independent of the tree’s topology, but that this is not the case for the spr and tbr operations. We also give tight upper and lower bounds for the size of the neighborhood of a binary tree for the spr and tbr operations and characterize those trees for which these bounds are attained. more...
- Published
- 2014
- Full Text
- View/download PDF
50. 2D tree object representation via the slope chain code
- Author
-
Ernesto Bribiesca and Guadalupe Bribiesca-Contreras
- Subjects
Radial tree ,Discrete mathematics ,K-ary tree ,Segment tree ,Interval tree ,Search tree ,Range tree ,Tree traversal ,Tree structure ,Artificial Intelligence ,Signal Processing ,Computer Vision and Pattern Recognition ,Software ,Mathematics - Abstract
A method for representing 2D (two-dimensional) tree objects is described. This representation is based on a chain code, which is called the Slope Chain Code (SCC). Thus, 2D tree objects are described by means of a chain of element strings suitably combined by means of parentheses. These 2D tree objects correspond to naturally existing 2D tree structures. This tree notation preserves the shape of trees (and the shape of their branches), allows us to know their topological and geometrical properties. The proposed notation of 2D tree objects is invariant under translation, rotation and, optionally, under scaling. Also, it is possible to define a unique start vertex for each tree via the unique path in the tree. Using this notation it is possible to obtain the mirror image of any tree with ease. Furthermore, two interesting properties of trees are presented: the accumulated slope and the tortuosity. Tortuosity is a very important property of trees and has many applications in different fields. In order to prove our method for representing 2D tree objects, we obtain some tree descriptors of tree objects and compute their measures of accumulated slope and tortuosity. Finally, we present some examples of 2D trees from the real world about echinoderm species identification. more...
- Published
- 2014
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.