@conference {16829,
	title = {Distance Oracles for Spatial Networks},
	booktitle = {Data Engineering, 2009. ICDE {\textquoteright}09. IEEE 25th International Conference on},
	year = {2009},
	month = {2009/04/29/2},
	pages = {652 - 663},
	abstract = {The popularity of location-based services and the need to do real-time processing on them has led to an interest in performing queries on transportation networks, such as finding shortest paths and finding nearest neighbors. The challenge is that these operations involve the computation of distance along a spatial network rather than "as the crow flies." In many applications an estimate of the distance is sufficient, which can be achieved by use of an oracle. An approximate distance oracle is proposed for spatial networks that exploits the coherence between the spatial position of vertices and the network distance between them. Using this observation, a distance oracle is introduced that is able to obtain the epsiv-approximate network distance between two vertices of the spatial network. The network distance between every pair of vertices in the spatial network is efficiently represented by adapting the well-separated pair technique to spatial networks. Initially, use is made of an epsilon-approximate distance oracle of size O(n/epsiv<sup>d</sup>) that is capable of retrieving the approximate network distance in O(log n) time using a B-tree. The retrieval time can be theoretically reduced further to O(1) time by proposing another epsiv-approximate distance oracle of size O(n log n/epsiv<sup>d</sup>) that uses a hash table. Experimental results indicate that the proposed technique is scalable and can be applied to sufficiently large road networks. A 10\%-approximate oracle (epsiv = 0.1) on a large network yielded an average error of 0.9\% with 90\% of the answers making an error of 2\% or less and an average retrieval timeof 68 mu seconds. Finally, a strategy for the integration of the distance oracle into any relational database system as well as using it to perform a variety of spatial queries such as region search, k-nearest neighbor search, and spatial joins on spatial networks is discussed.},
	keywords = {B-tree;distance, data, database, databases;tree, distance;hash, languages;query, neighbor, network, network;transportation, networks;spatial, networks;well-separated, oracles;epsiv-approximate, pair, processing;region, processing;relational, search;location-based, search;relational, services;real-time, structures;, system;road, table;k-nearest, technique;programming},
	doi = {10.1109/ICDE.2009.53},
	author = {Sankaranarayanan,J. and Samet, Hanan}
}
@conference {13335,
	title = {The half-edge tree: a compact data structure for level-of-detail tetrahedral meshes},
	booktitle = {Shape Modeling and Applications, 2005 International Conference},
	year = {2005},
	month = {2005/06//},
	pages = {332 - 337},
	abstract = {We propose a new data structure for the compact encoding of a level-of detail (LOD) model of a three-dimensional scalar field based on unstructured tetrahedral meshes. Such data structure, called a half-edge tree (HET), is built through the iterative application of a half-edge collapse, i.e. by contracting an edge to one of its endpoints. We also show that selective refined meshes extracted from an HET contain on average about 34\% and up to 75\% less tetrahedra than those extracted from an LOD model built through a general edge collapse.},
	keywords = {application;, compact, computational, data, detection;, edge, encoding;, generation;, geometry;, half-edge, iterative, level-of-detail, mesh, meshes;, methods;, model;, structure;, structures;, tetrahedral, tree, tree;},
	doi = {10.1109/SMI.2005.47},
	author = {Danovaro,E. and De Floriani, Leila and Magillo,P. and Puppo,E. and Sobrero,D. and Sokolovsky,N.}
}
@conference {18017,
	title = {Arbitrate-and-move primitives for high throughput on-chip interconnection networks},
	booktitle = {Circuits and Systems, 2004. ISCAS {\textquoteright}04. Proceedings of the 2004 International Symposium on},
	volume = {2},
	year = {2004},
	month = {2004/05//},
	pages = {II - 441-4 Vol.2 - II - 441-4 Vol.2},
	abstract = {An n-leaf pipelined balanced binary tree is used for arbitration of order and movement of data from n input ports to one output port. A novel arbitrate-and-move primitive circuit for every node of the tree, which is based on a concept of reduced synchrony that benefits from attractive features of both asynchronous and synchronous designs, is presented. The design objective of the pipelined binary tree is to provide a key building block in a high-throughput mesh-of-trees interconnection network for Explicit Multi Threading (XMT) architecture, a recently introduced parallel computation framework. The proposed reduced synchrony circuit was compared with asynchronous and synchronous designs of arbitrate-and-move primitives. Simulations with 0.18 mu;m technology show that compared to an asynchronous design, the proposed reduced synchrony implementation achieves a higher throughput, up to 2 Giga-Requests per second on an 8-leaf binary tree. Our circuit also consumes less power than the synchronous design, and requires less silicon area than both the synchronous and asynchronous designs.},
	keywords = {8, arbiter, arbitrate-and-move, architecture;, asynchronous, balanced, binary, circuit, circuit;, circuits;, consumption;, data, explicit, interconnection, interconnections;, leaf, mesh-of-trees, multi-threading;, Multithreading, n-leaf, network;, pipeline, pipelined, power, primitive, processing;, reduced, simulation;, structures;, synchronous, synchrony, system-on-chip;, tree, tree;},
	doi = {10.1109/ISCAS.2004.1329303},
	author = {Balkan,A.O. and Gang Qu and Vishkin, Uzi}
}
@conference {12286,
	title = {Multi-dimensional quorum sets for read-few write-many replica control protocols},
	booktitle = {Cluster Computing and the Grid, 2004. CCGrid 2004. IEEE International Symposium on},
	year = {2004},
	month = {2004/04//},
	pages = {355 - 362},
	abstract = {We describe d-spaces, a replica control protocol defined in terms of quorum sets on multi-dimensional logical structures. Our work is motivated by asymmetrical access patterns, where the number of read accesses to data are dominant relative to update accesses, i.e. where the protocols should be read-few write-many. D-spaces are optimal with respect to quorum group sizes. The quality of the tradeoff between read efficiency and update availability is not matched by existing quorum protocols. We also propose a novel scheme for implementing d-spaces that combines caching and local information to provide a best-effort form of global views. This allows quorum reconfiguration to be lightweight without impacting access latencies, even when the rate of membership changes is very high.},
	keywords = {accesses;, availability;, cache, caching;, Communication, complexity;, CONTROL, d-spaces;, distributed, efficiency;, lightweight, logical, multi-dimensional, processing;, protocols;, quorum, read, read-few, reconfiguration;, replica, sets;, storage;, structures;, update, write-many},
	doi = {10.1109/CCGrid.2004.1336588},
	author = {Silaghi,B. and Keleher,P. and Bhattacharjee, Bobby}
}
@conference {15029,
	title = {Strategies for exploring large scale data},
	booktitle = {Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on},
	year = {2004},
	month = {2004/05//},
	pages = {2 - 2},
	abstract = {We consider the problem of querying large scale multidimensional time series data to discover events of interest, test and validate hypotheses, or to associate temporal patterns with specific events. This type of data currently dominates most other types of available data, and will very likely become even more prevalent in the future given the current trends in collecting time series of business, scientific, demographic, and simulation data. The ability to explore such collections interactively, even at a coarse level, will be critical in discovering the information and knowledge embedded in such collections. We develop indexing techniques and search algorithms to efficiently handle temporal range value querying of multidimensional time series data. Our indexing uses linear space data structures that enable the handling of queries in I/O time that is essentially the same as that of handling a single time slice, assuming the availability of a logarithmic number of processors as a function of the temporal window. A data structure with provably almost optimal asymptotic bounds is also presented for the case when the number of multidimensional objects is relatively small. These techniques improve significantly over standard techniques for either serial or parallel processing, and are evaluated by extensive experimental results that confirm their superior performance.},
	keywords = {algorithms;, association;, asymptotic, bounds;, business, data, data;, database, databases;, demographic, discovery;, Indexing, indexing;, information, knowledge, large, linear, mining;, multidimensional, objects;, optimal, Parallel, pattern, processing;, query, querying;, range, scale, scientific, search, serial, series, series;, simulation, space, structure;, structures;, techniques;, temporal, TIME, value, very, window;},
	doi = {10.1109/ISPAN.2004.1300447},
	author = {JaJa, Joseph F.}
}
@conference {14387,
	title = {PXML: a probabilistic semistructured data model and algebra},
	booktitle = {Data Engineering, 2003. Proceedings. 19th International Conference on},
	year = {2003},
	month = {2003/03//},
	pages = {467 - 478},
	abstract = {Despite the recent proliferation of work on semistructured data models, there has been little work to date on supporting uncertainty in these models. We propose a model for probabilistic semistructured data (PSD). The advantage of our approach is that it supports a flexible representation that allows the specification of a wide class of distributions over semistructured instances. We provide two semantics for the model and show that the semantics are probabilistically coherent. Next, we develop an extension of the relational algebra to handle probabilistic semistructured data and describe efficient algorithms for answering queries that use this algebra. Finally, we present experimental results showing the efficiency of our algorithms.},
	keywords = {algebra;, data, databases;, instances;, model;, models;, probabilistic, processing;, PXML;, query, relational, semistructured, structures;, tree, XML;},
	doi = {10.1109/ICDE.2003.1260814},
	author = {Hung,E. and Getoor, Lise and V.S. Subrahmanian}
}
@conference {14961,
	title = {Efficient techniques for range search queries on earth science data},
	booktitle = {Scientific and Statistical Database Management, 2002. Proceedings. 14th International Conference on},
	year = {2002},
	month = {2002///},
	pages = {142 - 151},
	abstract = {We consider the problem of organizing large scale earth science raster data to efficiently handle queries for identifying regions whose parameters fall within certain range values specified by the queries. This problem seems to be critical to enabling basic data mining tasks such as determining associations between physical phenomena and spatial factors, detecting changes and trends, and content based retrieval. We assume that the input is too large to fit in internal memory and hence focus on data structures and algorithms that minimize the I/O bounds. A new data structure, called a tree-of-regions (ToR), is introduced and involves a combination of an R-tree and efficient representation of regions. It is shown that such a data structure enables the handling of range queries in an optimal I/O time, under certain reasonable assumptions. We also show that updates to the ToR can be handled efficiently. Experimental results for a variety of multi-valued earth science data illustrate the fast execution times of a wide range of queries, as predicted by our theoretical analysis.},
	keywords = {based, computing;, content, data, data;, databases;, Earth, factors;, large, mining, mining;, natural, processing;, queries;, query, range, raster, retrieval;, scale, Science, sciences, search, spatial, structures;, tasks;, temporal, tree, tree-of-regions;, visual},
	doi = {10.1109/SSDM.2002.1029714},
	author = {Shi,Qingmin and JaJa, Joseph F.}
}
@conference {16150,
	title = {SpaceTree: supporting exploration in large node link tree, design evolution and empirical evaluation},
	booktitle = {Information Visualization, 2002. INFOVIS 2002. IEEE Symposium on},
	year = {2002},
	month = {2002///},
	pages = {57 - 64},
	abstract = {We present a novel tree browser that builds on the conventional node link tree diagrams. It adds dynamic rescaling of branches of the tree to best fit the available screen space, optimized camera movement, and the use of preview icons summarizing the topology of the branches that cannot be expanded. In addition, it includes integrated search and filter functions. This paper reflects on the evolution of the design and highlights the principles that emerged from it. A controlled experiment showed benefits for navigation to already previously visited nodes and estimation of overall tree topology.},
	keywords = {browser;, camera, data, design, diagrams;, dynamic, evolution;, experiment;, exploration;, filter, functions;, graphical, icons;, integrated, interfaces;, large, link, movement;, node, novel, optimized, rescaling;, search;, SpaceTree;, structures;, topology;, tree, user, visualisation;, visualization;},
	doi = {10.1109/INFVIS.2002.1173148},
	author = {Plaisant, Catherine and Grosjean,J. and Bederson, Benjamin B.}
}
@conference {17962,
	title = {Skip Strips: maintaining triangle strips for view-dependent rendering},
	booktitle = {Visualization {\textquoteright}99. Proceedings},
	year = {1999},
	month = {1999/10//},
	pages = {131 - 518},
	abstract = {View-dependent simplification has emerged as a powerful tool for graphics acceleration in visualization of complex environments. However, view-dependent simplification techniques have not been able to take full advantage of the underlying graphics hardware. Specifically, triangle strips are a widely used hardware-supported mechanism to compactly represent and efficiently render static triangle meshes. However, in a view-dependent framework, the triangle mesh connectivity changes at every frame, making it difficult to use triangle strips. We present a novel data structure, Skip Strip, that efficiently maintains triangle strips during such view-dependent changes. A Skip Strip stores the vertex hierarchy nodes in a skip-list-like manner with path compression. We anticipate that Skip Strips will provide a road map to combine rendering acceleration techniques for static datasets, typical of retained-mode graphics applications, with those for dynamic datasets found in immediate-mode applications.},
	keywords = {(computer, Acceleration, acceleration;graphics, applications;path, applications;skip-list-like, changes;view-dependent, compression;rendering, connectivity;triangle, data, datasets;graphics, datasets;static, environments;data, equipment;data, graphic, Graphics, graphics);spatial, hardware;hardware-supported, hierarchy, manner;static, mechanism;immediate-mode, mesh, meshes;triangle, nodes;view-dependent, rendering;view-dependent, simplification;visualization;computer, Skip, Strips;complex, strips;vertex, structure;dynamic, structures;, techniques;retained-mode, triangle, visualisation;rendering},
	doi = {10.1109/VISUAL.1999.809877},
	author = {El-Sana,J. and Azanli,E. and Varshney, Amitabh}
}
@conference {18038,
	title = {Efficient approximate and dynamic matching of patterns using a labeling paradigm},
	booktitle = {Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on},
	year = {1996},
	month = {1996/10//},
	pages = {320 - 328},
	abstract = {A key approach in string processing algorithmics has been the labeling paradigm which is based on assigning labels to some of the substrings of a given string. If these labels are chosen consistently, they can enable fast comparisons of substrings. Until the first optimal parallel algorithm for suffix tree construction was given by the authors in 1994 the labeling paradigm was considered not to be competitive with other approaches. They show that this general method is also useful for several central problems in the area of string processing: approximate string matching, dynamic dictionary matching, and dynamic text indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern ldquo;approximately rdquo;, i.e., with at most m differences. The differences can be in the form of inserted, deleted, or replaced characters. The text indexing problem deals with finding all occurrences of a pattern in a text, after the text is preprocessed. In the dynamic text indexing problem, updates to the text in the form of insertions and deletions of substrings are permitted. The dictionary matching problem deals with finding all occurrences of each pattern set of a set of patterns in a text, after the pattern set is preprocessed. In the dynamic dictionary matching problem, insertions and deletions of patterns to the pattern set are permitted},
	keywords = {algorithm;replaced, algorithmics;substrings;suffix, algorithms;pattern, approximate, characters;dynamic, characters;labeling, characters;string, complexity;indexing;parallel, construction;computational, data, dictionary, dynamic, indexing;efficient, matching;deleted, matching;dynamic, matching;efficient, matching;inserted, matching;string, matching;tree, paradigm;optimal, Parallel, pattern, PROCESSING, string, structures;, text, tree},
	doi = {10.1109/SFCS.1996.548491},
	author = {Sahinalp,S. C and Vishkin, Uzi}
}
@conference {13571,
	title = {Image based typographic analysis of documents},
	booktitle = {Document Analysis and Recognition, 1993., Proceedings of the Second International Conference on},
	year = {1993},
	month = {1993/10//},
	pages = {769 - 773},
	abstract = {An approach to image based typographic analysis of documents is provided. The problem requires a spatial understanding of the document layout as well as knowledge of the proper syntax. The system performs a page synthesis from the stream of formatting commands defined in a DVI file. Since the two-dimensional relationships between document components are not explicit in the page language, the authors develop a representation which preserves the two-dimensional layout, the read-order and the attributes of document components. From this hierarchical representation of the page layout we extract and analyze relevant typographic features such as margins, line and character spacing, and figure placement},
	keywords = {2D, analysis;, attributes;, based, character, commands;, component, data, description, document, DVI, extraction;, feature, figure, file;, formatting, hierarchical, image, language;, languages;, layout;, line, margins;, page, placement;, processing;, read-order;, relationships;, representation;, spacing;, spatial, structures;, syntax;, synthesis;, typographic, understanding;},
	doi = {10.1109/ICDAR.1993.395624},
	author = {David Doermann and Furuta,R.}
}
