Sachverhalt: A. A.a. Die Staatsanwaltschaft des Kantons Basel-Stadt führt gegen A._ ein Strafverfahren wegen Delikten gegen die sexuelle Integrität, Brandstiftung, mehrfacher Sachbeschädigung, mehrfacher Irreführung der Rechtspflege, mehrfachen Betrugs, Drohung und weiterer Delikte. A._ wurde am 26. März 2015 festgenommen und durch das Zwangsmassnahmengericht des Kantons Basel-Stadt mit Verfügung vom 28. März 2015 in Untersuchungshaft versetzt. A.b. In ihrem Antrag auf Anordnung der Untersuchungshaft hatte die Staatsanwaltschaft Folgendes dargelegt: Im Gebäude an der G._strasse ... in Basel, wo sich A._ mit seinem Nachtclub "B._" eingemietet habe, sei es 2013 und 2014 zu Sachbeschädigungen mit Säure und Farbe gekommen. Diese beträfen im Wesentlichen jene Geschosse, in welchen die anderen Mieter wohnten. Verschiedene Personen hätten Angaben gemacht, die auf eine Täterschaft von A._ hindeuteten. Dieser habe mit dem Liegenschaftseigentümer Streit und auch mit den anderen Mietern bestünden Probleme, da sie sich über Nachtlärm beklagt hätten. In der Nacht vom 13. auf den 14. Juli 2014 sei ein Fenster des Personenwagens von C._ eingeschlagen und der Innenraum mit Säure übergossen worden. Dasselbe sei in der Nacht vom 25. auf den 26. Januar 2015 mit dem Personenwagen von D._ geschehen. Beide Geschädigten würden A._ verdächtigen, weil sein Nachtclub ihnen gegenüber unberechtigte finanzielle Forderungen erhoben habe. Am 19. Mai 2013 sei ein Fahrzeug (Hummer) der E._ AG, welche durch A._ vertreten werde, abgebrannt. Ermittlungen hätten ergeben, dass von Brandstiftung auszugehen sei und dass ein Mobiltelefon, das gemäss den Angaben von A._ gegenüber der Polizei und gegenüber der Hausratsversicherung mitverbrannt sein soll, später immer noch in Betrieb war. F._ habe ausgesagt, dass A._ ihm erzählt habe, vergeblich versucht zu haben, seinen Hummer zu verkaufen. Die Ermittlungen hätten weiter ergeben, dass bei dem Fahrzeug der Kilometerstand um knapp 15'000 km zurückgestellt worden war. Auf die Anzeige des Liegenschaftseigentümers seien im Gebäude an der G._strasse ... im Korridor des 1. OG sowie im Nachtclub zahlreiche versteckte Kameras entdeckt worden, dies auch in den Séparées des Nachtclubs. Der Beschuldigte sei geständig, Rauchmelder mit Kameras erworben und montiert zu haben. F._ und D._ hätten ausgesagt, dass A._ in seinem Nachtclub den Gästen Kokain zur Verfügung stelle. Anlässlich einer Hausdurchsuchung vom 26. März 2015 am Wohnort von A._ seien drei Ampullen Anabolika und Munition zum Vorschein gekommen. Die Tänzerin H._ habe am 13. Januar 2015 gegen A._ Strafanzeige erhoben wegen Nötigung, Förderung der Prostitution sowie Ausnützung sexueller Handlungen. C._ habe zudem zu Protokoll gegeben, dass seine Ehefrau früher als Tänzerin im Nachtclub "B._" gearbeitet habe. Wegen ihrer Liebe zu ihm habe sie ihren Arbeitsvertrag vorzeitig auflösen wollen. A._ habe daraufhin Fr. 30'000.-- pro Monat verlangt. Auch werde den Tänzerinnen, wenn sie mit seinen Methoden nicht einverstanden seien, gedroht, man werde mit ihnen in den Wald fahren, dort würde man dann sehen. Schliesslich habe F._ ausgesagt, eine Tänzerin namens I._ (J._) habe ihm gesagt, dass A._ mit seinen Tänzerinnen gegen ihren Willen Sex habe. A.c. Am 7. April 2015 stellte A._ ein Haftentlassungsgesuch, das vom Zwangsmassnahmengericht mit Verfügung vom 16. April 2015 abgewiesen wurde. Eine von A._ dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt mit Entscheid vom 13. Mai 2015 ab. B. Mit Beschwerde in Strafsachen vom 29. Mai 2015 ans Bundesgericht beantragt A._, der Entscheid des Appellationsgerichts sei aufzuheben und er selbst sei sofort aus der Untersuchungshaft zu entlassen. Das Appellationsgericht und die Staatsanwaltschaft beantragen die Abweisung der Beschwerde. Der Beschwerdeführer hält in seiner Stellungnahme dazu an seinen Anträgen und Rechtsauffassungen fest.