Author name cluster

Hanan Samet

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TIST Journal 2020 Journal Article

Querying Recurrent Convoys over Trajectory Data

Munkh-Erdene Yadamjav
Zhifeng Bao
Baihua Zheng
Farhana M. Choudhury
Hanan Samet

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. We observe that existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the co-moving pattern. In this study, we propose the problem of finding recurrent co-moving patterns from streaming trajectories, enabling us to discover recent co-moving patterns that are repeated within a given time period. Experimental results on real-life trajectory data verify the efficiency and effectiveness of our method.

Details DOI

NeurIPS Conference 2017 Conference Paper

Training Quantized Nets: A Deeper Understanding

Hao Li
Soham De
Zheng Xu
Christoph Studer
Hanan Samet
Tom Goldstein

Currently, deep neural networks are deployed on low-power portable devices by first training a full-precision model using powerful hardware, and then deriving a corresponding low-precision model for efficient inference on such systems. However, training models directly with coarsely quantized weights is a key step towards learning on embedded platforms that have limited computing resources, memory capacity, and power consumption. Numerous recent publications have studied methods for training quantized networks, but these studies have mostly been empirical. In this work, we investigate training methods for quantized neural networks from a theoretical viewpoint. We first explore accuracy guarantees for training methods under convexity assumptions. We then look at the behavior of these algorithms for non-convex problems, and show that training algorithms that exploit high-precision representations have an important greedy search phase that purely quantized training methods lack, which explains the difficulty of training using low-precision arithmetic.

PDF Details

FOCS Conference 1999 Conference Paper

Efficient Regular Data Structures and Algorithms for Location and Proximity Problems

Arnon Amir
Alon Efrat
Piotr Indyk
Hanan Samet

Investigates data structures obtained by a recursive partitioning of the input domain into regions of equal size. One of the most well-known examples of such a structure is the quadtree, which is used in this paper as a basis for more complex data structures; we also provide multidimensional versions of the stratified tree of P. van Emde Boas (1997). We show that, under the assumption that the input points have limited precision (i. e. are drawn from an integer grid of size u), these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for finding the dynamic approximate nearest neighbor (under insertions and deletions) and the exact online closest pair (under insertions only) in any constant dimension. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear-time (optimal) algorithm for computing the expansion of a shape represented by a quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the dilation by a ball operation.

Details

ICRA Conference 1990 Conference Paper

Motion planning in a dynamic domain

Kikuo Fujimura
Hanan Samet

Motion planning is studied in a time-varying environment. Each obstacle is a convex polygon that moves in a fixed direction at a constant speed. The robot is a convex polygon that is subject to a speed bound. A method of determining whether or not there is a translational collision-free motion for a polygonal robot from an initial position to a final position and of planning such a motion, if it exists, is presented. The method makes use of the concept of configuration spaces and accessibility. An algorithm is given for motion planning in such an environment, and its time complexity is analyzed. >

Details

ICRA Conference 1989 Conference Paper

Time-minimal paths among moving obstacles

Kikuo Fujimura
Hanan Samet

Motion planning for a point robot is studied in a two-dimensional time-varying environment. The obstacle is a convex polygon that moves in a fixed direction at a constant speed. The point to be reached (referred to as the destination point) also moves along a known path. The concept of accessibility from a point to a moving object is introduced, and it is used to define a graph on a set of moving obstacles. The graph is shown to exhibit an important property, that is, if the moving point is able to move faster than any of the obstacles, a time-minimal path is given as a sequence of edges in the graph. An algorithm is described for generating a time-minimal path, and its execution time is analyzed. >

Details

ICRA Conference 1988 Conference Paper

Path planning among moving obstacles using spatial indexing

Kikuo Fujimura
Hanan Samet

A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, a path is generated for a mobile robot that navigates in the two-dimensional plane. Time is included as one of the dimensions of the model world. This allows the moving obstacles to be regarded as stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles and must navigate within the predetermined range of velocity, acceleration, and centrifugal force. A spatial index is used to facilitate geometric search for the path-planning task. Computer simulation results are presented to illustrate the feasibility of this approach. >

Details