@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/epsivd) 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/epsivd) 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 {16836, title = {High-Dimensional Similarity Retrieval Using Dimensional Choice}, booktitle = {Similarity Search and Applications, 2008. SISAP 2008. First International Workshop on}, year = {2008}, month = {2008/04//}, pages = {35 - 42}, abstract = {There are several pieces of information that can be utilized in order to improve the efficiency of similarity searches on high-dimensional data. The most commonly used information is the distribution of the data itself but the use of dimensional choice based on the information in the query as well as the parameters of the distribution can provide an effective improvement in the query processing speed and storage. The use of this method can produce dimension reduction by as much as a factor of n, the number of data points in the database, over sequential search. We demonstrate that the curse of dimensionality is not based on the dimension of the data itself, but primarily upon the effective dimension of the distance function. We also introduce a new distance function that utilizes fewer dimensions of the higher dimensional space to produce a maximal lower bound distance in order to approximate the full distance function. This work has demonstrated significant dimension reduction, up to 70\% reduction with an improvement in accuracy or over 99\% with only a 6\% loss in accuracy on a prostate cancer data set.}, keywords = {data, database, function;high-dimensional, management, processing;, processing;sequential, reduction;database, reduction;distance, retrieval;query, search;data, search;similarity, similarity, system;dimension, systems;query}, doi = {10.1109/SISAP.2008.20}, author = {Tahmoush,D. and Samet, Hanan} } @article {13421, title = {Amino acid quantitative structure property relationship database: a web-based platform for quantitative investigations of amino acids}, journal = {Protein Engineering Design and SelectionProtein Engineering, Design and Selection}, volume = {20}, year = {2007}, month = {2007/07/01/}, pages = {347 - 351}, abstract = {Here, we present the AA-QSPR Db (Amino Acid Quantitative Structure Property Relationship Database): a novel, freely available web-resource of data pertaining to amino acids, both engineered and naturally occurring. In addition to presenting fundamental molecular descriptors of size, charge and hydrophobicity, it also includes online visualization tools for users to perform instant, interactive analyses of amino acid sub-sets in which they are interested. The database has been designed with extensible markup language technology to provide a flexible structure, suitable for future development. In addition to providing easy access for queries by external computers, it also offers a user-friendly web-based interface that facilitates human interactions (submission, storage and retrieval of amino acid data) and an associated e-forum that encourages users to question and discuss current and future database contents.}, keywords = {Amino acids, database, QSPR, XML}, isbn = {1741-0126, 1741-0134}, doi = {10.1093/protein/gzm027}, url = {http://peds.oxfordjournals.org/content/20/7/347}, author = {Lu,Yi and Bulka,Blazej and desJardins, Marie and Freeland,Stephen J} } @conference {16847, title = {Indexing Point Triples Via Triangle Geometry}, booktitle = {Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on}, year = {2007}, month = {2007/04//}, pages = {936 - 945}, abstract = {Database search for images containing icons with specific mutual spatial relationships can be facilitated by an appropriately structured index. For the case of images containing subsets each of which consist of three icons, the one-to-one correspondence between (distinct) point triples and triangles allows the use of such triangle attributes as position, size, orientation, and "shape" in constructing a point-based index, in which each triangle maps to a single point in a resulting hyperdimensional index space. Size (based on the triangle perimeter) can be represented by a single linear dimension. The abstract "shape" of a triangle induces a space that is inherently two-dimensional, and a number of alternative definitions of a basis for this space are examined. Within a plane, orientation reduces to rotation, and (after assignment of a reference direction for the triangle) can be represented by a single, spatially closed dimension. However, assignment of a reference direction for triangles possessing a k-fold rotational symmetry presents a significant challenge. Methods are described for characterizing shape and orientation of triangles, and for mapping these attributes onto a set of linear axes to form a combined index. The shape attribute is independent of size, orientation, and position, and the characterization of shape and orientation is stable with respect to small variations in the indexed triangles.}, keywords = {database, databases;, dimension;spatial, geometry;database, hyperdimensional, index, index;single, index;triangle, indexing;query, linear, point;k-fold, processing;visual, relationships;structured, rotational, search;indexing, space;image, symmetry;point-based}, doi = {10.1109/ICDE.2007.367939}, author = {Cranston,C.B. and Samet, Hanan} } @conference {12685, title = {Facial similarity across age, disguise, illumination and pose}, booktitle = {Image Processing, 2004. ICIP {\textquoteright}04. 2004 International Conference on}, volume = {3}, year = {2004}, month = {2004/10//}, pages = {1999 - 2002 Vol. 3 - 1999 - 2002 Vol. 3}, abstract = {Illumination, pose variations, disguises, aging effects and expression variations are some of the key factors that affect the performance of face recognition systems. Face recognition systems have always been studied from a recognition perspective. Our emphasis is on deriving a measure of similarity between faces. The similarity measure provides insights into the role each of the above mentioned variations play in affecting the performance of face recognition systems. In the process of computing the similarity measure between faces, we suggest a framework to compensate for pose variations and introduce the notion of {\textquoteright}half-faces{\textquoteright} to circumvent the problem of non-uniform illumination. We used the similarity measure to retrieve similar faces from a database containing multiple images of individuals. Moreover, we devised experiments to study the effect age plays in affecting facial similarity. In conclusion, the similarity measure helps in studying the significance facial features play in affecting the performance of face recognition systems.}, keywords = {Aging, database, databases;, disguise;, effect;, Expression, Face, half-face;, illumination;, image, lighting;, pose, recognition, recognition;, retrieval;, system;, variation;, visual}, doi = {10.1109/ICIP.2004.1421474}, author = {Ramanathan,N. and Chellapa, Rama and Roy Chowdhury, A.K.} } @conference {12695, title = {Probabilistic identity characterization for face recognition}, booktitle = {Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on}, volume = {2}, year = {2004}, month = {2004/07/02/june}, pages = {II-805 - II-812 Vol.2 - II-805 - II-812 Vol.2}, abstract = {We present a general framework for characterizing the object identity in a single image or a group of images with each image containing a transformed version of the object, with applications to face recognition. In terms of the transformation, the group is made of either many still images or frames of a video sequence. The object identity is either discrete- or continuous-valued. This probabilistic framework integrates all the evidence of the set and handles the localization problem, illumination and pose variations through subspace identity encoding. Issues and challenges arising in this framework are addressed and efficient computational schemes are presented. Good face recognition results using the PIE database are reported.}, keywords = {characterization;, database, database;, encoding;, Face, identity, identity;, image, localization, management, object, PIE, probabilistic, problem;, recognition;, sequence;, sequences;, subspace, systems;, video}, doi = {10.1109/CVPR.2004.1315247}, author = {Zhou,S. K and Chellapa, Rama} } @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 {17892, title = {A high performance multi-perspective vision studio}, booktitle = {Proceedings of the 17th annual international conference on Supercomputing}, series = {ICS {\textquoteright}03}, year = {2003}, month = {2003///}, pages = {348 - 357}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {We describe a multi-perspective vision studio as a flexible high performance framework for solving complex image processing and machine vision problems on multi-view image sequences. The studio abstracts multi-view image data from image sequence acquisition facilities, stores and catalogs sequences in a high performance distributed database, allows customization of back-end processing services, and can serve custom client applications, thus helping make multi-view video sequence processing efficient and generic. To illustrate our approach, we describe two multi-perspective studio applications, and discuss performance and scalability results.}, keywords = {database, distributed system, high-performance, IMAGE PROCESSING, multi-perspective, VISION, volumetric reconstruction}, isbn = {1-58113-733-8}, doi = {10.1145/782814.782862}, url = {http://doi.acm.org/10.1145/782814.782862}, author = {Borovikov,Eugene and Sussman, Alan} } @article {17809, title = {Temporal probabilistic object bases}, journal = {Knowledge and Data Engineering, IEEE Transactions on}, volume = {15}, year = {2003}, month = {2003/08//july}, pages = {921 - 939}, abstract = {There are numerous applications where we have to deal with temporal uncertainty associated with objects. The ability to automatically store and manipulate time, probabilities, and objects is important. We propose a data model and algebra for temporal probabilistic object bases (TPOBs), which allows us to specify the probability with which an event occurs at a given time point. In explicit TPOB-instances, the sets of time points along with their probability intervals are explicitly enumerated. In implicit TPOB-instances, sets of time points are expressed by constraints and their probability intervals by probability distribution functions. Thus, implicit object base instances are succinct representations of explicit ones; they allow for an efficient implementation of algebraic operations, while their explicit counterparts make defining algebraic operations easy. We extend the relational algebra to both explicit and implicit instances and prove that the operations on implicit instances correctly implement their counterpart on explicit instances.}, keywords = {algebra;, algebraic, bases;, constraints;, data, database, database;, databases;, distribution, explicit, functions;, handling;, implicit, instances;, integrity;, intervals;, management;, model;, models;, object, object-oriented, operations;, probabilistic, probability, probability;, relational, temporal, theory;, Uncertainty, uncertainty;}, isbn = {1041-4347}, doi = {10.1109/TKDE.2003.1209009}, author = {Biazzo,V. and Giugno,R. and Lukasiewicz,T. and V.S. Subrahmanian} } @conference {16914, title = {Content-based image retrieval using Fourier descriptors on a logo database}, booktitle = {Pattern Recognition, 2002. Proceedings. 16th International Conference on}, volume = {3}, year = {2002}, month = {2002///}, pages = {521 - 524 vol.3 - 521 - 524 vol.3}, abstract = {A system that enables the pictorial specification of queries in an image database is described. The queries are comprised of rectangle, polygon, ellipse, and B-spline shapes. The queries specify which shapes should appear in the target image as well as spatial constraints on the distance between them and their relative position. The retrieval process makes use of an abstraction of the contour of the shape which is invariant against translation, scale, rotation, and starting point, that is based on the use of Fourier descriptors. These abstractions are used in a system to locate logos in an image database. The utility of this approach is illustrated using some sample queries.}, keywords = {abstraction;, analysis;, constraints;, content-based, contour, database, database;, databases;, descriptors;, detection;, edge, Fourier, image, logos;, pictorial, processing;, query, retrieval;, SHAPE, spatial, specification;, theory;, visual}, doi = {10.1109/ICPR.2002.1047991}, author = {Folkers,A. and Samet, Hanan} } @conference {18470, title = {Virtual audio system customization using visual matching of ear parameters}, booktitle = {16th International Conference on Pattern Recognition, 2002. Proceedings}, volume = {3}, year = {2002}, month = {2002///}, pages = {1003- 1006 vol.3 - 1003- 1006 vol.3}, publisher = {IEEE}, organization = {IEEE}, abstract = {Applications in the creation of virtual auditory spaces (VAS) and sonification require individualized head related transfer functions (HRTFs) for perceptual fidelity. HRTFs exhibit significant variation from person to person due to differences between their pinnae, and their body sizes. We propose and preliminarily implement a simple HRTF customization based on the use of a published database of HRTFs (Algazi et al., 2001) that also contains geometrical measurements of subject pinnae. We measure some of these features via simple image processing, and select the HRTF that has features most closely corresponding to the individual{\textquoteright}s features. This selection procedure is implemented along with the virtual auditory system described in (Zotkin et al., 2002), and listener tests conducted comparing the customized HRTF and a fixed HRTF. Despite the simplicity of the method, tests reveal average improvement in localization accuracy of about 25 percent, though performance improvement varies with source location and individuals.}, keywords = {acoustic signal processing, Audio systems, Auditory system, Computer vision, database, Ear, ear parameter matching, geometrical measurements, Head, head related transfer functions, HRTF customization, Image databases, IMAGE PROCESSING, medical image processing, performance improvement, Position measurement, sonification, Spatial databases, System testing, Transfer functions, virtual audio system customization, virtual auditory spaces, virtual auditory system, visual matching}, isbn = {0-7695-1695-X}, doi = {10.1109/ICPR.2002.1048207}, author = {Zotkin,Dmitry N and Duraiswami, Ramani and Davis, Larry S. and Mohan,A. and Raykar,V.} } @conference {13612, title = {OCR-based rate-distortion analysis of residual coding}, booktitle = {Image Processing, 1997. Proceedings., International Conference on}, volume = {3}, year = {1997}, month = {1997/10//}, pages = {690 -693 vol.3 - 690 -693 vol.3}, abstract = {Symbolic compression of document images provides access to symbols found in document images and exploits the redundancy found within them. Document images are highly structured and contain large numbers of repetitive symbols. We have shown that while symbolically compressing a document image we are able to perform compressed-domain processing. Symbolic compression forms representative prototypes for symbols and encode the image by the location of these prototypes and a residual (the difference between symbol and prototype). We analyze the rate-distortion tradeoff by varying the amount of residual used in compression for both distance- and row-order coding. A measure of distortion is based on the performance of an OCR system on the resulting image. The University of Washington document database images, ground truth, and OCR evaluation software are used for experiments}, keywords = {analysis;redundancy;representative, character, coding;distortion, coding;image, coding;lossy, coding;row-order, coding;symbolic, compression;data, compression;document, compression;lossy, database, distortion, Evaluation, image, images;document, images;experiments;ground, measure;document, OCR, of, performance;University, processing;distance-order, processing;image, prototypes;residual, recognition;rate, representation;optical, representation;progressive, software;OCR, system, theory;, transmission;rate-distortion, truth;image, Washington;compressed-domain}, doi = {10.1109/ICIP.1997.632215}, author = {Kia,O. E and David Doermann} } @article {17231, title = {Incremental data structures and algorithms for dynamic query interfaces}, journal = {ACM SIGMOD Record}, volume = {25}, year = {1996}, month = {1996/12//}, pages = {21 - 24}, abstract = {Dynamic query interfaces (DQIs) form a recently developed method of database access that provides continuous realtime feedback to the user during the query formulation process. Previous work shows that DQIs are elegant and powerful interfaces to small databases. Unfortunately, when applied to large databases, previous DQI algorithms slow to a crawl. We present a new approach to DQI algorithms that works well with large databases.}, keywords = {algorithm, data structure, database, direct manipulation, dynamic query, Information Visualization, user interface}, isbn = {0163-5808}, doi = {10.1145/245882.245891}, url = {http://doi.acm.org/10.1145/245882.245891}, author = {Tanin,Egemen and Beigel,Richard and Shneiderman, Ben} } @conference {14838, title = {2D images of 3-D oriented points}, booktitle = {Computer Vision and Pattern Recognition, 1993. Proceedings CVPR {\textquoteright}93., 1993 IEEE Computer Society Conference on}, year = {1993}, month = {1993/06//}, pages = {226 - 232}, abstract = {A number of vision problems have been shown to become simpler when one models projection from 3-D to 2-D as a nonrigid linear transformation. These results have been largely restricted to models and scenes that consist only of 3-D points. It is shown that, with this projection model, several vision tasks become fundamentally more complex in the somewhat more complicated domain of oriented points. More space is required for indexing models in a database, more images are required to derive structure from motion, and new views of an object cannot be synthesized linearly from old views}, keywords = {2D, 3-D, database, derivation;, image, images;, indexing;, linear, model, nonrigid, oriented, points;, processing;, recovery;, structure-form-motion, structure-from-motion, transformation;}, doi = {10.1109/CVPR.1993.340985}, author = {Jacobs, David W.} }