• R.U. Abbasi, M. Abe, M. Abou Bakr Othman, T.Abu-Zayyad, M. Allen, R. Anderson, R. Azuma, E. Barcikowski, J.W. Belz, D.R. Bergman, D. Besson, S.A. Blake, M. Byrne, R. Cady, M.J. Chae, B.G. Cheon, J. Chiba, M. Chikawa, W.R. Cho, B. Farhang-Boroujeny, T. Fujii, M. Fukushima, W.H. Gillman, T. Goto, W. Hanlon, J.C. Hanson, Y. Hayashi, N. Hayashida, K. Hibino, K. Honda, D. Ikeda, N. Inoue, T. Ishii, R. Ishimori, H. Ito, D. Ivanov, C. Jayanthmurthy, C.C.H. Jui, K. Kadota, F. Kakimoto, O. Kalashev, K. Kasahara, H. Kawai, S. Kawakami, S. Kawana, K. Kawata, E. Kido, H.B. Kim, J.H. Kim, J.H. Kim, S. Kitamura, Y. Kitamura, S. Kunwar, V. Kuzmin, Y.J. Kwon, J. Lan, S.I. Lim, J.P. Lundquist, K. Machida, K. Martens, T. Matsuda, T. Matsuyama, J.N. Matthews, M. Minamino, K. Mukai, I. Myers, K. Nagasawa, S. Nagataki, T. Nakamura, T. Nonaka, A. Nozato, S. Ogio, J. Ogura, M. Ohnishi, H. Ohoka, K. Oki, T. Okuda, M. Ono, A. Oshima, S. Ozawa, I.H. Park, S. Prohira, M.S. Pshirkov, A. Rezazadeh-Reyhani, D.C. Rodriguez, G. Rubtsov, D. Ryu, H. Sagawa, N. Sakurai, A.L. Sampson, L.M. Scott, D. Schurig, P.D. Shah, F. Shibata, T. Shibata, H. Shimodaira, B.K. Shin, J.D. Smith, P. Sokolsky, R.W. Springer, B.T. Stokes, S.R. Stratton, T.A. Stroman, T. Suzawa, H. Takai, M. Takamura, M. Takeda, R. Takeishi, A. Taketa, M. Takita, Y. Tameda, H. Tanaka, K. Tanaka, M. Tanaka, S.B. Thomas, G.B. Thomson, P. Tinyakov, I. Tkachev, H. Tokuno, T. Tomida, S. Troitsky, Y. Tsunesada, K. Tsutsumi, Y. Uchihori, S. Udo, F. Urban, G. Vasiloff, S. Venkatesh, T. Wong, R. Yamane, H. Yamaoka, K. Yamazaki, J. Yang, K. Yashiro, Y. Yoneda, S. Yoshida, H. Yoshii, R. Zollinger, Z. Zundel
    March 16, 2016 astro-ph.IM
    TARA (Telescope Array Radar) is a cosmic ray radar detection experiment colocated with Telescope Array, the conventional surface scintillation detector (SD) and fluorescence telescope detector (FD) near Delta, Utah, U.S.A. The TARA detector combines a 40 kW, 54.1 MHz VHF transmitter and high-gain transmitting antenna which broadcasts the radar carrier over the SD array and within the FD field of view, towards a 250 MS/s DAQ receiver. TARA has been collecting data since 2013 with the primary goal of observing the radar signatures of extensive air showers (EAS). Simulations indicate that echoes are expected to be short in duration (~10 microseconds) and exhibit rapidly changing frequency, with rates on the order of 1 MHz/microsecond. The EAS radar cross-section (RCS) is currently unknown although it is the subject of over 70 years of speculation. A novel signal search technique is described in which the expected radar echo of a particular air shower is used as a matched filter template and compared to waveforms obtained by triggering the radar DAQ using the Telescope Array fluorescence detector. No evidence for the scattering of radio frequency radiation by EAS is obtained to date. We report the first quantitative RCS upper limits using EAS that triggered the Telescope Array Fluorescence Detector.
  • We study three-way joins on MapReduce. Joins are very useful in a multitude of applications from data integration and traversing social networks, to mining graphs and automata-based constructions. However, joins are expensive, even for moderate data sets; we need efficient algorithms to perform distributed computation of joins using clusters of many machines. MapReduce has become an increasingly popular distributed computing system and programming paradigm. We consider a state-of-the-art MapReduce multi-way join algorithm by Afrati and Ullman and show when it is appropriate for use on very large data sets. By providing a detailed experimental study, we demonstrate that this algorithm scales much better than what is suggested by the original paper. However, if the join result needs to be summarized or aggregated, as opposed to being only enumerated, then the aggregation step can be integrated into a cascade of two-way joins, making it more efficient than the other algorithm, and thus becomes the preferred solution.
  • Regret minimizing sets are a very recent approach to representing a dataset D with a small subset S of representative tuples. The set S is chosen such that executing any top-1 query on S rather than D is minimally perceptible to any user. To discover an optimal regret minimizing set of a predetermined cardinality is conjectured to be a hard problem. In this paper, we generalize the problem to that of finding an optimal k$regret minimizing set, wherein the difference is computed over top-k queries, rather than top-1 queries. We adapt known geometric ideas of top-k depth contours and the reverse top-k problem. We show that the depth contours themselves offer a means of comparing the optimality of regret minimizing sets using L2 distance. We design an O(cn^2) plane sweep algorithm for two dimensions to compute an optimal regret minimizing set of cardinality c. For higher dimensions, we introduce a greedy algorithm that progresses towards increasingly optimal solutions by exploiting the transitivity of L2 distance.
  • We consider the recently introduced monochromatic reverse top-k queries which ask for, given a new tuple q and a dataset D, all possible top-k queries on D union {q} for which q is in the result. Towards this problem, we focus on designing indexes in two dimensions for repeated (or batch) querying, a novel but practical consideration. We present the insight that by representing the dataset as an arrangement of lines, a critical k-polygon can be identified and used exclusively to respond to reverse top-k queries. We construct an index based on this observation which has guaranteed worst-case query cost that is logarithmic in the size of the k-polygon. We implement our work and compare it to related approaches, demonstrating that our index is fast in practice. Furthermore, we demonstrate through our experiments that a k-polygon is comprised of a small proportion of the original data, so our index structure consumes little disk space.
  • In this paper, we present a method for recognising an agent's behaviour in dynamic, noisy, uncertain domains, and across multiple levels of abstraction. We term this problem on-line plan recognition under uncertainty and view it generally as probabilistic inference on the stochastic process representing the execution of the agent's plan. Our contributions in this paper are twofold. In terms of probabilistic inference, we introduce the Abstract Hidden Markov Model (AHMM), a novel type of stochastic processes, provide its dynamic Bayesian network (DBN) structure and analyse the properties of this network. We then describe an application of the Rao-Blackwellised Particle Filter to the AHMM which allows us to construct an efficient, hybrid inference method for this model. In terms of plan recognition, we propose a novel plan recognition framework based on the AHMM as the plan execution model. The Rao-Blackwellised hybrid inference for AHMM can take advantage of the independence properties inherent in a model of plan execution, leading to an algorithm for online probabilistic plan recognition that scales well with the number of levels in the plan hierarchy. This illustrates that while stochastic models for plan execution can be complex, they exhibit special structures which, if exploited, can lead to efficient plan recognition algorithms. We demonstrate the usefulness of the AHMM framework via a behaviour recognition system in a complex spatial environment using distributed video surveillance data.
  • Exchange bias effect is an important attribute in several device applications. Traditionally, it is discussed as a form of exchange anisotropy at the interface between the ferromagnetic/antiferromagnetic layers of two distinct systems. We report here on the magnetically ordered alloys possessing the feature of unidirectional anisotropy, which reverses its sign across a characteristic temperature. These are admixed rare earth intermetallics, comprising two dissimilar rare earth (RE) ions, belonging to the two different halves of the 4f-series and imbibing the notion of ferromagnetic coupling between the spins of all 4f-rare earth ions and that of the conduction electrons. Magnetic moments of dissimilar RE ions in such admixed alloys, however, get antiferromagnetically coupled and they display magnetic compensation feature such that the field induced reversal in the orientation of the magnetic moments of dissimilar rare earth ions happens across the compensation temperature (Tcomp). Above a threshold field, the conduction electron polarization also reverses its sign across Tcomp, this is argued to correlate with the observed phase reversal in the exchange bias field.
  • We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is the predecessor of x in S?" can be answered efficiently. We study this problem in the cell probe model introduced by Yao. Recently, Beame and Fich obtained optimal bounds on the number of probes needed by any deterministic query scheme if the associated storage scheme uses only n^{O(1)} cells of word size (\log m)^{O(1)} bits. We give a new lower bound proof for this problem that matches the bounds of Beame and Fich. Our lower bound proof has the following advantages: it works for randomised query schemes too, while Beame and Fich's proof works for deterministic query schemes only. It also extends to `quantum address-only' query schemes that we define in this paper, and is simpler than Beame and Fich's proof. We prove our lower bound using the round elimination approach of Miltersen, Nisan, Safra and Wigderson. Using tools from information theory, we prove a strong round elimination lemma for communication complexity that enables us to obtain a tight lower bound for the predecessor problem. Our strong round elimination lemma also extends to quantum communication complexity. We also use our round elimination lemma to obtain a rounds versus communication tradeoff for the `greater-than' problem, improving on the tradeoff in Miltersen et al. We believe that our round elimination lemma is of independent interest and should have other applications.
  • We introduce a new model for studying quantum data structure problems -- the "quantum cell probe model". We prove a lower bound for the static predecessor problem in the address-only version of this model where we allow quantum parallelism only over the `address lines' of the queries. The address-only quantum cell probe model subsumes the classical cell probe model, and many quantum query algorithms like Grover's algorithm fall into this framework. Our lower bound improves the previous known lower bound for the predecessor problem in the classical cell probe model with randomised query schemes, and matches the classical deterministic upper bound of Beame and Fich. Beame and Fich have also proved a matching lower bound for the predecessor problem, but only in the classical deterministic setting. Our lower bound has the advantage that it holds for the more general quantum model, and also, its proof is substantially simpler than that of Beame and Fich. We prove our lower bound by obtaining a round elimination lemma for quantum communication complexity. A similar lemma was proved by Miltersen, Nisan, Safra and Wigderson for classical communication complexity, but it was not strong enough to prove a lower bound matching the upper bound of Beame and Fich. Our quantum round elimination lemma also allows us to prove rounds versus communication tradeoffs for some quantum communication complexity problems like the "greater-than" problem. We also study the "static membership" problem in the quantum cell probe model. Generalising a result of Yao, we show that if the storage scheme is implicit, that is it can only store members of the subset and `pointers', then any quantum query scheme must make $\Omega(\log n)$ probes.
  • We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and randomized models. In this paper, we formulate this problem in the "quantum bitprobe model" and show tradeoff results between space and time.In this model, the storage scheme is classical but the query scheme is quantum.We show, roughly speaking, that similar lower bounds hold in the quantum model as in the classical model, which imply that the classical upper bounds are more or less tight even in the quantum case. Our lower bounds are proved using linear algebraic techniques.