Location-dependent query is a service that enables users to acquire real-time location-dependent information on mobile objects. This type of service is challenged by the size and volatility of the underlying data. This challenge has created the need for new methods that allow users to efficiently access, retrieve, and update volatile mobile object data. Motivated by this necessity, this chapter explores and discusses research challenges and issues regarding indexing and querying mobile data. The support for predictive queries on road-network constrained mobile objects is a major deficiency in the existing research. This chapter also presents performance evaluation on some solutions of indexing mobile objects as well as their supported predictive queries under the road-network constraints.